home *** CD-ROM | disk | FTP | other *** search
/ Danny Amor's Online Library / Danny Amor's Online Library - Volume 1.iso / html / rfc / rfcxxxx / rfc1144 < prev    next >
Text File  |  1995-07-25  |  118KB  |  2,842 lines

  1.  
  2.  
  3.  
  4.  
  5.    Network Working Group                                     V. Jacobson/1/
  6.    Request for Comments: 1144                                           LBL
  7.                                                               February 1990
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.                           Compressing TCP/IP Headers
  17.  
  18.                           for Low-Speed Serial Links
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.    Status of this Memo
  30.  
  31.    This RFC is a proposed elective protocol for the Internet community and
  32.    requests discussion and suggestions for improvement.  It describes a
  33.    method for compressing the headers of TCP/IP datagrams to improve
  34.    performance over low speed serial links.  The motivation, implementation
  35.    and performance of the method are described.  C code for a sample
  36.    implementation is given for reference.  Distribution of this memo is
  37.    unlimited.
  38.  
  39.  
  40.  
  41.  
  42.    NOTE: Both ASCII and Postscript versions of this document are available.
  43.          The ASCII version, obviously, lacks all the figures and all the
  44.      information encoded in typographic variation (italics, boldface,
  45.      etc.).  Since this information was, in the author's opinion, an
  46.      essential part of the document, the ASCII version is at best
  47.      incomplete and at worst misleading.  Anyone who plans to work
  48.      with this protocol is strongly encouraged obtain the Postscript
  49.      version of this RFC.
  50.  
  51.  
  52.  
  53.  
  54.    ----------------------------
  55.      1. This work was supported in part by the U.S. Department of Energy
  56.    under Contract Number DE-AC03-76SF00098.
  57.  
  58.  
  59.  
  60.  
  61.    Contents
  62.  
  63.  
  64.    1  Introduction                                                        1
  65.  
  66.  
  67.    2  The problem                                                         1
  68.  
  69.  
  70.    3  The compression algorithm                                           4
  71.  
  72.       3.1 The basic idea . . . . . . . . . . . . . . . . . . . . . . . .  4
  73.  
  74.       3.2 The ugly details . . . . . . . . . . . . . . . . . . . . . . .  5
  75.  
  76.          3.2.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . .  5
  77.  
  78.          3.2.2 Compressed packet format. . . . . . . . . . . . . . . . .  7
  79.  
  80.          3.2.3 Compressor processing . . . . . . . . . . . . . . . . . .  8
  81.  
  82.          3.2.4 Decompressor processing . . . . . . . . . . . . . . . . . 12
  83.  
  84.  
  85.    4  Error handling                                                     14
  86.  
  87.       4.1 Error detection  . . . . . . . . . . . . . . . . . . . . . . . 14
  88.  
  89.       4.2 Error recovery . . . . . . . . . . . . . . . . . . . . . . . . 17
  90.  
  91.  
  92.    5  Configurable parameters and tuning                                 18
  93.  
  94.       5.1 Compression configuration  . . . . . . . . . . . . . . . . . . 18
  95.  
  96.       5.2 Choosing a maximum transmission unit . . . . . . . . . . . . . 20
  97.  
  98.       5.3 Interaction with data compression  . . . . . . . . . . . . . . 21
  99.  
  100.  
  101.    6  Performance measurements                                           23
  102.  
  103.  
  104.    7  Acknowlegements                                                    25
  105.  
  106.  
  107.    A  Sample Implementation                                              27
  108.  
  109.       A.1 Definitions and State Data . . . . . . . . . . . . . . . . . . 28
  110.  
  111.       A.2 Compression  . . . . . . . . . . . . . . . . . . . . . . . . . 31
  112.  
  113.  
  114.                                       i
  115.  
  116.  
  117.  
  118.  
  119.       A.3 Decompression  . . . . . . . . . . . . . . . . . . . . . . . . 37
  120.  
  121.       A.4 Initialization . . . . . . . . . . . . . . . . . . . . . . . . 41
  122.  
  123.       A.5 Berkeley Unix dependencies . . . . . . . . . . . . . . . . . . 41
  124.  
  125.  
  126.    B  Compatibility with past mistakes                                   43
  127.  
  128.       B.1 Living without a framing `type' byte . . . . . . . . . . . . . 43
  129.  
  130.       B.2 Backwards compatible SLIP servers  . . . . . . . . . . . . . . 43
  131.  
  132.  
  133.    C  More aggressive compression                                        45
  134.  
  135.  
  136.    D  Security Considerations                                            46
  137.  
  138.  
  139.    E  Author's address                                                   46
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.                                       ii
  173.  
  174.    RFC 1144               Compressing TCP/IP Headers          February 1990
  175.  
  176.  
  177.    1  Introduction
  178.  
  179.  
  180.    As increasingly powerful computers find their way into people's homes,
  181.    there is growing interest in extending Internet connectivity to those
  182.    computers.  Unfortunately, this extension exposes some complex problems
  183.    in link-level framing, address assignment, routing, authentication and
  184.    performance.  As of this writing there is active work in all these
  185.    areas.  This memo describes a method that has been used to improve
  186.    TCP/IP performance over low speed (300 to 19,200 bps) serial links.
  187.  
  188.    The compression proposed here is similar in spirit to the Thinwire-II
  189.    protocol described in [5].  However, this protocol compresses more
  190.    effectively (the average compressed header is 3 bytes compared to 13 in
  191.    Thinwire-II) and is both efficient and simple to implement (the Unix
  192.    implementation is 250 lines of C and requires, on the average, 90us (170
  193.    instructions) for a 20MHz MC68020 to compress or decompress a packet).
  194.  
  195.    This compression is specific to TCP/IP datagrams./2/  The author
  196.    investigated compressing UDP/IP datagrams but found that they were too
  197.    infrequent to be worth the bother and either there was insufficient
  198.    datagram-to-datagram coherence for good compression (e.g., name server
  199.    queries) or the higher level protocol headers overwhelmed the cost of
  200.    the UDP/IP header (e.g., Sun's RPC/NFS). Separately compressing the IP
  201.    and the TCP portions of the datagram was also investigated but rejected
  202.    since it increased the average compressed header size by 50% and doubled
  203.    the compression and decompression code size.
  204.  
  205.  
  206.    2  The problem
  207.  
  208.  
  209.    Internet services one might wish to access over a serial IP link from
  210.    home range from interactive `terminal' type connections (e.g., telnet,
  211.    rlogin, xterm) to bulk data transfer (e.g., ftp, smtp, nntp).  Header
  212.    compression is motivated by the need for good interactive response.
  213.    I.e., the line efficiency of a protocol is the ratio of the data to
  214.    header+data in a datagram.  If efficient bulk data transfer is the only
  215.    objective, it is always possible to make the datagram large enough to
  216.    approach an efficiency of 100%.
  217.  
  218.    Human-factors studies[15] have found that interactive response is
  219.    perceived as `bad' when low-level feedback (character echo) takes longer
  220.  
  221.    ----------------------------
  222.      2. The tie to TCP is deeper than might be obvious.  In addition to the
  223.    compression `knowing' the format of TCP and IP headers, certain features
  224.    of TCP have been used to simplify the compression protocol.  In
  225.    particular, TCP's reliable delivery and the byte-stream conversation
  226.    model have been used to eliminate the need for any kind of error
  227.    correction dialog in the protocol (see sec. 4).
  228.  
  229.  
  230.    Jacobson                                                        [Page 1]
  231.  
  232.    RFC 1144               Compressing TCP/IP Headers          February 1990
  233.  
  234.  
  235.    than 100 to 200 ms.  Protocol headers interact with this threshold three
  236.    ways:
  237.  
  238.    (1) If the line is too slow, it may be impossible to fit both the
  239.        headers and data into a 200 ms window:  One typed character results
  240.        in a 41 byte TCP/IP packet being sent and a 41 byte echo being
  241.        received.  The line speed must be at least 4000 bps to handle these
  242.        82 bytes in 200 ms.
  243.  
  244.    (2) Even with a line fast enough to handle packetized typing echo (4800
  245.        bps or above), there may be an undesirable interaction between bulk
  246.        data and interactive traffic:  For reasonable line efficiency the
  247.        bulk data packet size needs to be 10 to 20 times the header size.
  248.        I.e., the line maximum transmission unit or MTU should be 500 to
  249.        1000 bytes for 40 byte TCP/IP headers.  Even with type-of-service
  250.        queuing to give priority to interactive traffic, a telnet packet has
  251.        to wait for any in-progress bulk data packet to finish.  Assuming
  252.        data transfer in only one direction, that wait averages half the MTU
  253.        or 500 ms for a 1024 byte MTU at 9600 bps.
  254.  
  255.    (3) Any communication medium has a maximum signalling rate, the Shannon
  256.        limit.  Based on an AT&T study[2], the Shannon limit for a typical
  257.        dialup phone line is around 22,000 bps.  Since a full duplex, 9600
  258.        bps modem already runs at 80% of the limit, modem manufacturers are
  259.        starting to offer asymmetric allocation schemes to increase
  260.        effective bandwidth:  Since a line rarely has equivalent amounts of
  261.        data flowing both directions simultaneously, it is possible to give
  262.        one end of the line more than 11,000 bps by either time-division
  263.        multiplexing a half-duplex line (e.g., the Telebit Trailblazer) or
  264.        offering a low-speed `reverse channel' (e.g., the USR Courier
  265.        HST)./3/ In either case, the modem dynamically tries to guess which
  266.        end of the conversation needs high bandwidth by assuming one end of
  267.        the conversation is a human (i.e., demand is limited to <300 bps by
  268.        typing speed).  The factor-of-forty bandwidth multiplication due to
  269.        protocol headers will fool this allocation heuristic and cause these
  270.        modems to `thrash'.
  271.  
  272.    From the above, it's clear that one design goal of the compression
  273.    should be to limit the bandwidth demand of typing and ack traffic to at
  274.    most 300 bps.  A typical maximum typing speed is around five characters
  275.  
  276.  
  277.  
  278.    ----------------------------
  279.      3. See the excellent discussion of two-wire dialup line capacity in
  280.    [1], chap. 11.  In particular, there is widespread misunderstanding of
  281.    the capabilities of `echo-cancelling' modems (such as those conforming
  282.    to CCITT V.32):  Echo-cancellation can offer each side of a two-wire
  283.    line the full line bandwidth but, since the far talker's signal adds to
  284.    the local `noise', not the full line capacity.  The 22Kbps Shannon limit
  285.    is a hard-limit on data rate through a two-wire telephone connection.
  286.  
  287.  
  288.    Jacobson                                                        [Page 2]
  289.  
  290.    RFC 1144               Compressing TCP/IP Headers          February 1990
  291.  
  292.  
  293.    per second/4/ which leaves a budget 30 - 5 = 25 characters for headers
  294.    or five bytes of header per character typed./5/  Five byte headers solve
  295.    problems (1) and (3) directly and, indirectly, problem (2):  A packet
  296.    size of 100--200 bytes will easily amortize the cost of a five byte
  297.    header and offer a user 95--98% of the line bandwidth for data.  These
  298.    short packets mean little interference between interactive and bulk data
  299.    traffic (see sec. 5.2).
  300.  
  301.    Another design goal is that the compression protocol be based solely on
  302.    information guaranteed to be known to both ends of a single serial link.
  303.    Consider the topology shown in fig. 1 where communicating hosts A and B
  304.    are on separate local area nets (the heavy black lines) and the nets are
  305.    connected by two serial links (the open lines between gateways C--D and
  306.    E--F)./6/ One compression possibility would be to convert each TCP/IP
  307.    conversation into a semantically equivalent conversation in a protocol
  308.    with smaller headers, e.g., to an X.25 call.  But, because of routing
  309.    transients or multipathing, it's entirely possible that some of the A--B
  310.    traffic will follow the A-C-D-B path and some will follow the A-E-F-B
  311.    path.  Similarly, it's possible that A->B traffic will flow A-C-D-B and
  312.    B->A traffic will flow B-F-E-A. None of the gateways can count on seeing
  313.    all the packets in a particular TCP conversation and a compression
  314.    algorithm that works for such a topology cannot be tied to the TCP
  315.    connection syntax.
  316.  
  317.    A physical link treated as two, independent, simplex links (one each
  318.    direction) imposes the minimum requirements on topology, routing and
  319.    pipelining.  The ends of each simplex link only have to agree on the
  320.    most recent packet(s) sent on that link.  Thus, although any compression
  321.    scheme involves shared state, this state is spatially and temporally
  322.  
  323.    ----------------------------
  324.      4. See [13].  Typing bursts or multiple character keystrokes such as
  325.    cursor keys can exceed this average rate by factors of two to four.
  326.    However the bandwidth demand stays approximately constant since the TCP
  327.    Nagle algorithm[8] aggregates traffic with a <200ms interarrival time
  328.    and the improved header-to-data ratio compensates for the increased
  329.    data.
  330.      5. A similar analysis leads to essentially the same header size limit
  331.    for bulk data transfer ack packets.  Assuming that the MTU has been
  332.    selected for `unobtrusive' background file transfers (i.e., chosen so
  333.    the packet time is 200--400 ms --- see sec. 5), there can be at most 5
  334.    data packets per second in the `high bandwidth' direction.  A reasonable
  335.    TCP implementation will ack at most every other data packet so at 5
  336.    bytes per ack the reverse channel bandwidth is 2.5 * 5 = 12.5 bytes/sec.
  337.      6. Note that although the TCP endpoints are A and B, in this example
  338.    compression/decompression must be done at the gateway serial links,
  339.    i.e., between C and D and between E and F. Since A and B are using IP,
  340.    they cannot know that their communication path includes a low speed
  341.    serial link.  It is clearly a requirement that compression not break the
  342.    IP model, i.e., that compression function between intermediate systems
  343.    and not just between end systems.
  344.  
  345.  
  346.    Jacobson                                                        [Page 3]
  347.  
  348.    RFC 1144               Compressing TCP/IP Headers          February 1990
  349.  
  350.  
  351.    local and adheres to Dave Clark's principle of fate sharing[4]:  The two
  352.    ends can only disagree on the state if the link connecting them is
  353.    inoperable, in which case the disagreement doesn't matter.
  354.  
  355.  
  356.  
  357.    3  The compression algorithm
  358.  
  359.  
  360.    3.1  The basic idea
  361.  
  362.    Figure 2 shows a typical (and minimum length) TCP/IP datagram header./7/
  363.    The header size is 40 bytes:  20 bytes of IP and 20 of TCP.
  364.    Unfortunately, since the TCP and IP protocols were not designed by a
  365.    committee, all these header fields serve some useful purpose and it's
  366.    not possible to simply omit some in the name of efficiency.
  367.  
  368.    However, TCP establishes connections and, typically, tens or hundreds of
  369.    packets are exchanged on each connection.  How much of the per-packet
  370.    information is likely to stay constant over the life of a connection?
  371.    Half---the shaded fields in fig. 3.  So, if the sender and receiver keep
  372.    track of active connections/8/ and the receiver keeps a copy of the
  373.    header from the last packet it saw from each connection, the sender gets
  374.    a factor-of-two compression by sending only a small (<= 8 bit)
  375.    connection identifier together with the 20 bytes that change and letting
  376.    the receiver fill in the 20 fixed bytes from the saved header.
  377.  
  378.    One can scavenge a few more bytes by noting that any reasonable
  379.    link-level framing protocol will tell the receiver the length of a
  380.    received message so total length (bytes 2 and 3) is redundant.  But then
  381.    the header checksum (bytes 10 and 11), which protects individual hops
  382.    from processing a corrupted IP header, is essentially the only part of
  383.    the IP header being sent.  It seems rather silly to protect the
  384.    transmission of information that isn't being transmitted.  So, the
  385.    receiver can check the header checksum when the header is actually sent
  386.    (i.e., in an uncompressed datagram) but, for compressed datagrams,
  387.    regenerate it locally at the same time the rest of the IP header is
  388.    being regenerated./9/
  389.  
  390.  
  391.    ----------------------------
  392.      7. The TCP and IP protocols and protocol headers are described in [10]
  393.    and [11].
  394.      8. The 96-bit tuple <src address, dst address, src port, dst port>
  395.    uniquely identifies a TCP connection.
  396.      9. The IP header checksum is not an end-to-end checksum in the sense
  397.    of [14]:  The time-to-live update forces the IP checksum to be
  398.    recomputed at each hop.  The author has had unpleasant personal
  399.    experience with the consequences of violating the end-to-end argument in
  400.    [14] and this protocol is careful to pass the end-to-end TCP checksum
  401.    through unmodified.  See sec. 4.
  402.  
  403.  
  404.    Jacobson                                                        [Page 4]
  405.  
  406.    RFC 1144               Compressing TCP/IP Headers          February 1990
  407.  
  408.  
  409.    This leaves 16 bytes of header information to send.  All of these bytes
  410.    are likely to change over the life of the conversation but they do not
  411.    all change at the same time.  For example, during an FTP data transfer
  412.    only the packet ID, sequence number and checksum change in the
  413.    sender->receiver direction and only the packet ID, ack, checksum and,
  414.    possibly, window, change in the receiver->sender direction.  With a copy
  415.    of the last packet sent for each connection, the sender can figure out
  416.    what fields change in the current packet then send a bitmask indicating
  417.    what changed followed by the changing fields./10/
  418.  
  419.    If the sender only sends fields that differ, the above scheme gets the
  420.    average header size down to around ten bytes.  However, it's worthwhile
  421.    looking at how the fields change:  The packet ID typically comes from a
  422.    counter that is incremented by one for each packet sent.  I.e., the
  423.    difference between the current and previous packet IDs should be a
  424.    small, positive integer, usually <256 (one byte) and frequently = 1.
  425.    For packets from the sender side of a data transfer, the sequence number
  426.    in the current packet will be the sequence number in the previous packet
  427.    plus the amount of data in the previous packet (assuming the packets are
  428.    arriving in order).  Since IP packets can be at most 64K, the sequence
  429.    number change must be < 2^16 (two bytes).  So, if the differences in the
  430.    changing fields are sent rather than the fields themselves, another
  431.    three or four bytes per packet can be saved.
  432.  
  433.    That gets us to the five-byte header target.  Recognizing a couple of
  434.    special cases will get us three byte headers for the two most common
  435.    cases---interactive typing traffic and bulk data transfer---but the
  436.    basic compression scheme is the differential coding developed above.
  437.    Given that this intellectual exercise suggests it is possible to get
  438.    five byte headers, it seems reasonable to flesh out the missing details
  439.    and actually implement something.
  440.  
  441.  
  442.    3.2  The ugly details
  443.  
  444.    3.2.1  Overview
  445.  
  446.    Figure 4 shows a block diagram of the compression software.  The
  447.    networking system calls a SLIP output driver with an IP packet to be
  448.  
  449.    ----------------------------
  450.     10. This is approximately Thinwire-I from [5].  A slight modification
  451.    is to do a `delta encoding' where the sender subtracts the previous
  452.    packet from the current packet (treating each packet as an array of 16
  453.    bit integers), then sends a 20-bit mask indicating the non-zero
  454.    differences followed by those differences.  If distinct conversations
  455.    are separated, this is a fairly effective compression scheme (e.g.,
  456.    typically 12-16 byte headers) that doesn't involve the compressor
  457.    knowing any details of the packet structure.  Variations on this theme
  458.    have been used, successfully, for a number of years (e.g., the Proteon
  459.    router's serial link protocol[3]).
  460.  
  461.  
  462.    Jacobson                                                        [Page 5]
  463.  
  464.    RFC 1144               Compressing TCP/IP Headers          February 1990
  465.  
  466.  
  467.    sent over the serial line.  The packet goes through a compressor which
  468.    checks if the protocol is TCP. Non-TCP packets and `uncompressible' TCP
  469.    packets (described below) are just marked as TYPE_IP and passed to a
  470.    framer.  Compressible TCP packets are looked up in an array of packet
  471.    headers.  If a matching connection is found, the incoming packet is
  472.    compressed, the (uncompressed) packet header is copied into the array,
  473.    and a packet of type COMPRESSED_TCP is sent to the framer.  If no match
  474.    is found, the oldest entry in the array is discarded, the packet header
  475.    is copied into that slot, and a packet of type UNCOMPRESSED_TCP is sent
  476.    to the framer.  (An UNCOMPRESSED_TCP packet is identical to the original
  477.    IP packet except the IP protocol field is replaced with a connection
  478.    number---an index into the array of saved, per-connection packet
  479.    headers.  This is how the sender (re-)synchronizes the receiver and
  480.    `seeds' it with the first, uncompressed packet of a compressed packet
  481.    sequence.)
  482.  
  483.    The framer is responsible for communicating the packet data, type and
  484.    boundary (so the decompressor can learn how many bytes came out of the
  485.    compressor).  Since the compression is a differential coding, the framer
  486.    must not re-order packets (this is rarely a concern over a single serial
  487.    link).  It must also provide good error detection and, if connection
  488.    numbers are compressed, must provide an error indication to the
  489.    decompressor (see sec. 4)./11/
  490.  
  491.    The decompressor does a `switch' on the type of incoming packets:  For
  492.    TYPE_IP, the packet is simply passed through.  For UNCOMPRESSED_TCP, the
  493.    connection number is extracted from the IP protocol field and
  494.    IPPROTO_TCP is restored, then the connection number is used as an index
  495.    into the receiver's array of saved TCP/IP headers and the header of the
  496.    incoming packet is copied into the indexed slot.  For COMPRESSED_TCP,
  497.    the connection number is used as an array index to get the TCP/IP header
  498.    of the last packet from that connection, the info in the compressed
  499.    packet is used to update that header, then a new packet is constructed
  500.    containing the now-current header from the array concatenated with the
  501.    data from the compressed packet.
  502.  
  503.    Note that the communication is simplex---no information flows in the
  504.    decompressor-to-compressor direction.  In particular, this implies that
  505.    the decompressor is relying on TCP retransmissions to correct the saved
  506.    state in the event of line errors (see sec. 4).
  507.  
  508.  
  509.  
  510.  
  511.  
  512.    ----------------------------
  513.     11. Link level framing is outside the scope of this document.  Any
  514.    framing that provides the facilities listed in this paragraph should be
  515.    adequate for the compression protocol.  However, the author encourages
  516.    potential implementors to see [9] for a proposed, standard, SLIP
  517.    framing.
  518.  
  519.  
  520.    Jacobson                                                        [Page 6]
  521.  
  522.    RFC 1144               Compressing TCP/IP Headers          February 1990
  523.  
  524.  
  525.    3.2.2  Compressed packet format
  526.  
  527.    Figure 5 shows the format of a compressed TCP/IP packet.  There is a
  528.    change mask that identifies which of the fields expected to change
  529.    per-packet actually changed, a connection number so the receiver can
  530.    locate the saved copy of the last packet for this TCP connection, the
  531.    unmodified TCP checksum so the end-to-end data integrity check will
  532.    still be valid, then for each bit set in the change mask, the amount the
  533.    associated field changed.  (Optional fields, controlled by the mask, are
  534.    enclosed in dashed lines in the figure.)  In all cases, the bit is set
  535.    if the associated field is present and clear if the field is absent./12/
  536.  
  537.    Since the delta's in the sequence number, etc., are usually small,
  538.    particularly if the tuning guidelines in section 5 are followed, all the
  539.    numbers are encoded in a variable length scheme that, in practice,
  540.    handles most traffic with eight bits:  A change of one through 255 is
  541.    represented in one byte.  Zero is improbable (a change of zero is never
  542.    sent) so a byte of zero signals an extension:  The next two bytes are
  543.    the MSB and LSB, respectively, of a 16 bit value.  Numbers larger than
  544.    16 bits force an uncompressed packet to be sent.  For example, decimal
  545.    15 is encoded as hex 0f, 255 as ff, 65534 as 00 ff fe, and zero as 00 00
  546.    00.  This scheme packs and decodes fairly efficiently:  The usual case
  547.    for both encode and decode executes three instructions on a MC680x0.
  548.  
  549.    The numbers sent for TCP sequence number and ack are the difference/13/
  550.    between the current value and the value in the previous packet (an
  551.    uncompressed packet is sent if the difference is negative or more than
  552.    64K). The number sent for the window is also the difference between the
  553.    current and previous values.  However, either positive or negative
  554.    changes are allowed since the window is a 16 bit field.  The packet's
  555.    urgent pointer is sent if URG is set (an uncompressed packet is sent if
  556.    the urgent pointer changes but URG is not set).  For packet ID, the
  557.    number sent is the difference between the current and previous values.
  558.    However, unlike the rest of the compressed fields, the assumed change
  559.    when I is clear is one, not zero.
  560.  
  561.    There are two important special cases:
  562.  
  563.    (1) The sequence number and ack both change by the amount of data in the
  564.        last packet; no window change or URG.
  565.  
  566.    (2) The sequence number changes by the amount of data in the last
  567.        packet, no ack or window change or URG.
  568.  
  569.    ----------------------------
  570.     12. The bit `P' in the figure is different from the others:  It is a
  571.    copy of the `PUSH' bit from the TCP header.  `PUSH' is a curious
  572.    anachronism considered indispensable by certain members of the Internet
  573.    community.  Since PUSH can (and does) change in any datagram, an
  574.    information preserving compression scheme must pass it explicitly.
  575.     13. All differences are computed using two's complement arithmetic.
  576.  
  577.  
  578.    Jacobson                                                        [Page 7]
  579.  
  580.    RFC 1144               Compressing TCP/IP Headers          February 1990
  581.  
  582.  
  583.    (1) is the case for echoed terminal traffic.  (2) is the sender side of
  584.    non-echoed terminal traffic or a unidirectional data transfer.  Certain
  585.    combinations of the S, A, W and U bits of the change mask are used to
  586.    signal these special cases.  `U' (urgent data) is rare so two unlikely
  587.    combinations are S W U (used for case 1) and S A W U (used for case 2).
  588.    To avoid ambiguity, an uncompressed packet is sent if the actual changes
  589.    in a packet are S * W U.
  590.  
  591.    Since the `active' connection changes rarely (e.g., a user will type for
  592.    several minutes in a telnet window before changing to a different
  593.    window), the C bit allows the connection number to be elided.  If C is
  594.    clear, the connection is assumed to be the same as for the last
  595.    compressed or uncompressed packet.  If C is set, the connection number
  596.    is in the byte immediately following the change mask./14/
  597.  
  598.    From the above, it's probably obvious that compressed terminal traffic
  599.    usually looks like (in hex):  0B c c d, where the 0B indicates case (1),
  600.    c c is the two byte TCP checksum and d is the character typed.  Commands
  601.    to vi or emacs, or packets in the data transfer direction of an FTP
  602.    `put' or `get' look like 0F c c d ... , and acks for that FTP look like
  603.    04 c c a where a is the amount of data being acked./15/
  604.  
  605.  
  606.    3.2.3  Compressor processing
  607.  
  608.    The compressor is called with the IP packet to be processed and the
  609.    compression state structure for the outgoing serial line.  It returns a
  610.    packet ready for final framing and the link level `type' of that packet.
  611.  
  612.    As the last section noted, the compressor converts every input packet
  613.    into either a TYPE_IP, UNCOMPRESSED_TCP or COMPRESSED_TCP packet.  A
  614.  
  615.  
  616.  
  617.    ----------------------------
  618.     14. The connection number is limited to one byte, i.e., 256
  619.    simultaneously active TCP connections.  In almost two years of
  620.    operation, the author has never seen a case where more than sixteen
  621.    connection states would be useful (even in one case where the SLIP link
  622.    was used as a gateway behind a very busy, 64-port terminal multiplexor).
  623.    Thus this does not seem to be a significant restriction and allows the
  624.    protocol field in UNCOMPRESSED_TCP packets to be used for the connection
  625.    number, simplifying the processing of those packets.
  626.     15. It's also obvious that the change mask changes infrequently and
  627.    could often be elided.  In fact, one can do slightly better by saving
  628.    the last compressed packet (it can be at most 16 bytes so this isn't
  629.    much additional state) and checking to see if any of it (except the TCP
  630.    checksum) has changed.  If not, send a packet type that means
  631.    `compressed TCP, same as last time' and a packet containing only the
  632.    checksum and data.  But, since the improvement is at most 25%, the added
  633.    complexity and state doesn't seem justified.  See appendix C.
  634.  
  635.  
  636.    Jacobson                                                        [Page 8]
  637.  
  638.    RFC 1144               Compressing TCP/IP Headers          February 1990
  639.  
  640.  
  641.    TYPE_IP packet is an unmodified copy/16/ of the input packet and
  642.    processing it doesn't change the compressor's state in any way.
  643.  
  644.    An UNCOMPRESSED_TCP packet is identical to the input packet except the
  645.    IP protocol field (byte 9) is changed from `6' (protocol TCP) to a
  646.    connection number.  In addition, the state slot associated with the
  647.    connection number is updated with a copy of the input packet's IP and
  648.    TCP headers and the connection number is recorded as the last connection
  649.    sent on this serial line (for the C compression described below).
  650.  
  651.    A COMPRESSED_TCP packet contains the data, if any, from the original
  652.    packet but the IP and TCP headers are completely replaced with a new,
  653.    compressed header.  The connection state slot and last connection sent
  654.    are updated by the input packet exactly as for an UNCOMPRESSED_TCP
  655.    packet.
  656.  
  657.    The compressor's decision procedure is:
  658.  
  659.      - If the packet is not protocol TCP, send it as TYPE_IP.
  660.  
  661.      - If the packet is an IP fragment (i.e., either the fragment offset
  662.        field is non-zero or the more fragments bit is set), send it as
  663.        TYPE_IP./17/
  664.  
  665.      - If any of the TCP control bits SYN, FIN or RST are set or if the ACK
  666.        bit is clear, consider the packet uncompressible and send it as
  667.        TYPE_IP./18/
  668.  
  669.    ----------------------------
  670.     16. It is not necessary (or desirable) to actually duplicate the input
  671.    packet for any of the three output types.  Note that the compressor
  672.    cannot increase the size of a datagram.  As the code in appendix A
  673.    shows, the protocol can be implemented so all header modifications are
  674.    made `in place'.
  675.     17. Only the first fragment contains the TCP header so the fragment
  676.    offset check is necessary.  The first fragment might contain a complete
  677.    TCP header and, thus, could be compressed.  However the check for a
  678.    complete TCP header adds quite a lot of code and, given the arguments in
  679.    [6], it seems reasonable to send all IP fragments uncompressed.
  680.     18. The ACK test is redundant since a standard conforming
  681.    implementation must set ACK in all packets except for the initial SYN
  682.    packet.  However, the test costs nothing and avoids turning a bogus
  683.    packet into a valid one.
  684.    SYN packets are not compressed because only half of them contain a valid
  685.    ACK field and they usually contain a TCP option (the max. segment size)
  686.    which the following packets don't.  Thus the next packet would be sent
  687.    uncompressed because the TCP header length changed and sending the SYN
  688.    as UNCOMPRESSED_TCP instead of TYPE_IP would buy nothing.
  689.    The decision to not compress FIN packets is questionable.  Discounting
  690.    the trick in appendix B.1, there is a free bit in the header that could
  691.    be used to communicate the FIN flag.  However, since connections tend to
  692.  
  693.  
  694.    Jacobson                                                        [Page 9]
  695.  
  696.    RFC 1144               Compressing TCP/IP Headers          February 1990
  697.  
  698.  
  699.    If a packet makes it through the above checks, it will be sent as either
  700.    UNCOMPRESSED_TCP or COMPRESSED_TCP:
  701.  
  702.      - If no connection state can be found that matches the packet's source
  703.        and destination IP addresses and TCP ports, some state is reclaimed
  704.        (which should probably be the least recently used) and an
  705.        UNCOMPRESSED_TCP packet is sent.
  706.  
  707.      - If a connection state is found, the packet header it contains is
  708.        checked against the current packet to make sure there were no
  709.        unexpected changes.  (E.g., that all the shaded fields in fig. 3 are
  710.        the same).  The IP protocol, fragment offset, more fragments, SYN,
  711.        FIN and RST fields were checked above and the source and destination
  712.        address and ports were checked as part of locating the state.  So
  713.        the remaining fields to check are protocol version, header length,
  714.        type of service, don't fragment, time-to-live, data offset, IP
  715.        options (if any) and TCP options (if any).  If any of these fields
  716.        differ between the two headers, an UNCOMPRESSED_TCP packet is sent.
  717.  
  718.    If all the `unchanging' fields match, an attempt is made to compress the
  719.    current packet:
  720.  
  721.      - If the URG flag is set, the urgent data field is encoded (note that
  722.        it may be zero) and the U bit is set in the change mask.
  723.        Unfortunately, if URG is clear, the urgent data field must be
  724.        checked against the previous packet and, if it changes, an
  725.        UNCOMPRESSED_TCP packet is sent.  (`Urgent data' shouldn't change
  726.        when URG is clear but [11] doesn't require this.)
  727.  
  728.      - The difference between the current and previous packet's window
  729.        field is computed and, if non-zero, is encoded and the W bit is set
  730.        in the change mask.
  731.  
  732.      - The difference between ack fields is computed.  If the result is
  733.        less than zero or greater than 2^16 - 1, an UNCOMPRESSED_TCP packet
  734.        is sent./19/  Otherwise, if the result is non-zero, it is encoded
  735.        and the A bit is set in the change mask.
  736.  
  737.      - The difference between sequence number fields is computed.  If the
  738.        result is less than zero or greater than 2^16 - 1, an
  739.  
  740.  
  741.  
  742.  
  743.  
  744.  
  745.    ----------------------------
  746.    last for many packets, it seemed unreasonable to dedicate an entire bit
  747.    to a flag that would only appear once in the lifetime of the connection.
  748.     19. The two tests can be combined into a single test of the most
  749.    significant 16 bits of the difference being non-zero.
  750.  
  751.  
  752.    Jacobson                                                       [Page 10]
  753.  
  754.    RFC 1144               Compressing TCP/IP Headers          February 1990
  755.  
  756.  
  757.        UNCOMPRESSED_TCP packet is sent./20/  Otherwise, if the result is
  758.        non-zero, it is encoded and the S bit is set in the change mask.
  759.  
  760.    Once the U, W, A and S changes have been determined, the special-case
  761.    encodings can be checked:
  762.  
  763.      - If U, S and W are set, the changes match one of the special-case
  764.        encodings.  Send an UNCOMPRESSED_TCP packet.
  765.  
  766.      - If only S is set, check if the change equals the amount of user data
  767.        in the last packet.  I.e., subtract the TCP and IP header lengths
  768.        from the last packet's total length field and compare the result to
  769.        the S change.  If they're the same, set the change mask to SAWU (the
  770.        special case for `unidirectional data transfer') and discard the
  771.        encoded sequence number change (the decompressor can reconstruct it
  772.        since it knows the last packet's total length and header length).
  773.  
  774.      - If only S and A are set, check if they both changed by the same
  775.        amount and that amount is the amount of user data in the last
  776.        packet.  If so, set the change mask to SWU (the special case for
  777.        `echoed interactive' traffic) and discard the encoded changes.
  778.  
  779.      - If nothing changed, check if this packet has no user data (in which
  780.        case it is probably a duplicate ack or window probe) or if the
  781.        previous packet contained user data (which means this packet is a
  782.        retransmission on a connection with no pipelining).  In either of
  783.        these cases, send an UNCOMPRESSED_TCP packet.
  784.  
  785.    Finally, the TCP/IP header on the outgoing packet is replaced with a
  786.    compressed header:
  787.  
  788.      - The change in the packet ID is computed and, if not one,/21/ the
  789.        difference is encoded (note that it may be zero or negative) and the
  790.        I bit is set in the change mask.
  791.  
  792.      - If the PUSH bit is set in the original datagram, the P bit is set in
  793.        the change mask.
  794.  
  795.      - The TCP and IP headers of the packet are copied to the connection
  796.        state slot.
  797.  
  798.  
  799.    ----------------------------
  800.     20. A negative sequence number change probably indicates a
  801.    retransmission.  Since this may be due to the decompressor having
  802.    dropped a packet, an uncompressed packet is sent to re-sync the
  803.    decompressor (see sec. 4).
  804.     21. Note that the test here is against one, not zero.  The packet ID is
  805.    typically incremented by one for each packet sent so a change of zero is
  806.    very unlikely.  A change of one is likely:  It occurs during any period
  807.    when the originating system has activity on only one connection.
  808.  
  809.  
  810.    Jacobson                                                       [Page 11]
  811.  
  812.    RFC 1144               Compressing TCP/IP Headers          February 1990
  813.  
  814.  
  815.      - The TCP and IP headers of the packet are discarded and a new header
  816.        is prepended consisting of (in reverse order):
  817.  
  818.          - the accumulated, encoded changes.
  819.  
  820.          - the TCP checksum (if the new header is being constructed `in
  821.            place', the checksum may have been overwritten and will have to
  822.            be taken from the header copy in the connection state or saved
  823.            in a temporary before the original header is discarded).
  824.  
  825.          - the connection number (if different than the last one sent on
  826.            this serial line).  This also means that the the line's last
  827.            connection sent must be set to the connection number and the C
  828.            bit set in the change mask.
  829.  
  830.          - the change mask.
  831.  
  832.    At this point, the compressed TCP packet is passed to the framer for
  833.    transmission.
  834.  
  835.  
  836.    3.2.4  Decompressor processing
  837.  
  838.    Because of the simplex communication model, processing at the
  839.    decompressor is much simpler than at the compressor --- all the
  840.    decisions have been made and the decompressor simply does what the
  841.    compressor has told it to do.
  842.  
  843.    The decompressor is called with the incoming packet,/22/ the length and
  844.    type of the packet and the compression state structure for the incoming
  845.    serial line.  A (possibly re-constructed) IP packet will be returned.
  846.  
  847.    The decompressor can receive four types of packet:  the three generated
  848.    by the compressor and a TYPE_ERROR pseudo-packet generated when the
  849.    receive framer detects an error./23/  The first step is a `switch' on
  850.    the packet type:
  851.  
  852.      - If the packet is TYPE_ERROR or an unrecognized type, a `toss' flag
  853.        is set in the state to force COMPRESSED_TCP packets to be discarded
  854.        until one with the C bit set or an UNCOMPRESSED_TCP packet arrives.
  855.        Nothing (a null packet) is returned.
  856.  
  857.    ----------------------------
  858.     22. It's assumed that link-level framing has been removed by this point
  859.    and the packet and length do not include type or framing bytes.
  860.     23. No data need be associated with a TYPE_ERROR packet.  It exists so
  861.    the receive framer can tell the decompressor that there may be a gap in
  862.    the data stream.  The decompressor uses this as a signal that packets
  863.    should be tossed until one arrives with an explicit connection number (C
  864.    bit set).  See the last part of sec. 4.1 for a discussion of why this is
  865.    necessary.
  866.  
  867.  
  868.    Jacobson                                                       [Page 12]
  869.  
  870.    RFC 1144               Compressing TCP/IP Headers          February 1990
  871.  
  872.  
  873.      - If the packet is TYPE_IP, an unmodified copy of it is returned and
  874.        the state is not modified.
  875.  
  876.      - If the packet is UNCOMPRESSED_TCP, the state index from the IP
  877.        protocol field is checked./24/  If it's illegal, the toss flag is
  878.        set and nothing is returned.  Otherwise, the toss flag is cleared,
  879.        the index is copied to the state's last connection received field, a
  880.        copy of the input packet is made,/25/ the TCP protocol number is
  881.        restored to the IP protocol field, the packet header is copied to
  882.        the indicated state slot, then the packet copy is returned.
  883.  
  884.    If the packet was not handled above, it is COMPRESSED_TCP and a new
  885.    TCP/IP header has to be synthesized from information in the packet plus
  886.    the last packet's header in the state slot.  First, the explicit or
  887.    implicit connection number is used to locate the state slot:
  888.  
  889.      - If the C bit is set in the change mask, the state index is checked.
  890.        If it's illegal, the toss flag is set and nothing is returned.
  891.        Otherwise, last connection received is set to the packet's state
  892.        index and the toss flag is cleared.
  893.  
  894.      - If the C bit is clear and the toss flag is set, the packet is
  895.        ignored and nothing is returned.
  896.  
  897.    At this point, last connection received is the index of the appropriate
  898.    state slot and the first byte(s) of the compressed packet (the change
  899.    mask and, possibly, connection index) have been consumed.  Since the
  900.    TCP/IP header in the state slot must end up reflecting the newly arrived
  901.    packet, it's simplest to apply the changes from the packet to that
  902.    header then construct the output packet from that header concatenated
  903.    with the data from the input packet.  (In the following description,
  904.    `saved header' is used as an abbreviation for `the TCP/IP header saved
  905.    in the state slot'.)
  906.  
  907.      - The next two bytes in the incoming packet are the TCP checksum.
  908.        They are copied to the saved header.
  909.  
  910.      - If the P bit is set in the change mask, the TCP PUSH bit is set in
  911.        the saved header.  Otherwise the PUSH bit is cleared.
  912.  
  913.  
  914.  
  915.  
  916.    ----------------------------
  917.     24. State indices follow the C language convention and run from 0 to N
  918.    - 1, where 0 < N <= 256 is the number of available state slots.
  919.     25. As with the compressor, the code can be structured so no copies are
  920.    done and all modifications are done in-place.  However, since the output
  921.    packet can be larger than the input packet, 128 bytes of free space must
  922.    be left at the front of the input packet buffer to allow room to prepend
  923.    the TCP/IP header.
  924.  
  925.  
  926.    Jacobson                                                       [Page 13]
  927.  
  928.    RFC 1144               Compressing TCP/IP Headers          February 1990
  929.  
  930.  
  931.      - If the low order four bits (S, A, W and U) of the change mask are
  932.        all set (the `unidirectional data' special case), the amount of user
  933.        data in the last packet is calculated by subtracting the TCP and IP
  934.        header lengths from the IP total length in the saved header.  That
  935.        amount is then added to the TCP sequence number in the saved header.
  936.  
  937.      - If S, W and U are set and A is clear (the `terminal traffic' special
  938.        case), the amount of user data in the last packet is calculated and
  939.        added to both the TCP sequence number and ack fields in the saved
  940.        header.
  941.  
  942.      - Otherwise, the change mask bits are interpreted individually in the
  943.        order that the compressor set them:
  944.  
  945.          - If the U bit is set, the TCP URG bit is set in the saved header
  946.            and the next byte(s) of the incoming packet are decoded and
  947.            stuffed into the TCP Urgent Pointer.  If the U bit is clear, the
  948.            TCP URG bit is cleared.
  949.  
  950.          - If the W bit is set, the next byte(s) of the incoming packet are
  951.            decoded and added to the TCP window field of the saved header.
  952.  
  953.          - If the A bit is set, the next byte(s) of the incoming packet are
  954.            decoded and added to the TCP ack field of the saved header.
  955.  
  956.          - If the S bit is set, the next byte(s) of the incoming packet are
  957.            decoded and added to the TCP sequence number field of the saved
  958.            header.
  959.  
  960.      - If the I bit is set in the change mask, the next byte(s) of the
  961.        incoming packet are decoded and added to the IP ID field of the
  962.        saved packet.  Otherwise, one is added to the IP ID.
  963.  
  964.    At this point, all the header information from the incoming packet has
  965.    been consumed and only data remains.  The length of the remaining data
  966.    is added to the length of the saved IP and TCP headers and the result is
  967.    put into the saved IP total length field.  The saved IP header is now up
  968.    to date so its checksum is recalculated and stored in the IP checksum
  969.    field.  Finally, an output datagram consisting of the saved header
  970.    concatenated with the remaining incoming data is constructed and
  971.    returned.
  972.  
  973.  
  974.    4  Error handling
  975.  
  976.  
  977.    4.1  Error detection
  978.  
  979.    In the author's experience, dialup connections are particularly prone to
  980.    data errors.  These errors interact with compression in two different
  981.    ways:
  982.  
  983.  
  984.    Jacobson                                                       [Page 14]
  985.  
  986.    RFC 1144               Compressing TCP/IP Headers          February 1990
  987.  
  988.  
  989.    First is the local effect of an error in a compressed packet.  All error
  990.    detection is based on redundancy yet compression has squeezed out almost
  991.    all the redundancy in the TCP and IP headers.  In other words, the
  992.    decompressor will happily turn random line noise into a perfectly valid
  993.    TCP/IP packet./26/  One could rely on the TCP checksum to detect
  994.    corrupted compressed packets but, unfortunately, some rather likely
  995.    errors will not be detected.  For example, the TCP checksum will often
  996.    not detect two single bit errors separated by 16 bits.  For a V.32 modem
  997.    signalling at 2400 baud with 4 bits/baud, any line hit lasting longer
  998.    than 400us. would corrupt 16 bits.  According to [2], residential phone
  999.    line hits of up to 2ms. are likely.
  1000.  
  1001.    The correct way to deal with this problem is to provide for error
  1002.    detection at the framing level.  Since the framing (at least in theory)
  1003.    can be tailored to the characteristics of a particular link, the
  1004.    detection can be as light or heavy-weight as appropriate for that
  1005.    link./27/  Since packet error detection is done at the framing level,
  1006.    the decompressor simply assumes that it will get an indication that the
  1007.    current packet was received with errors.  (The decompressor always
  1008.    ignores (discards) a packet with errors.  However, the indication is
  1009.    needed to prevent the error being propagated --- see below.)
  1010.  
  1011.    The `discard erroneous packets' policy gives rise to the second
  1012.    interaction of errors and compression.  Consider the following
  1013.    conversation:
  1014.  
  1015.                  +-------------------------------------------+
  1016.                  |original | sent   |received |reconstructed |
  1017.                  +---------+--------+---------+--------------+
  1018.                  | 1:  A   | 1:  A  | 1:  A   | 1:  A        |
  1019.                  | 2:  BC  | 1,  BC | 1,  BC  | 2:  BC       |
  1020.                  | 4:  DE  | 2,  DE |  ---    |  ---         |
  1021.                  | 6:  F   | 2,  F  | 2,  F   | 4:  F        |
  1022.                  | 7:  GH  | 1,  GH | 1,  GH  | 5:  GH       |
  1023.                  +-------------------------------------------+
  1024.  
  1025.    (Each entry above has the form `starting sequence number:data sent' or
  1026.    `?sequence number change,data sent'.)  The first thing sent is an
  1027.    uncompressed packet, followed by four compressed packets.  The third
  1028.    packet picks up an error and is discarded.  To reconstruct the fourth
  1029.    packet, the receiver applies the sequence number change from incoming
  1030.    compressed packet to the sequence number of the last correctly received
  1031.  
  1032.    ----------------------------
  1033.     26. modulo the TCP checksum.
  1034.     27. While appropriate error detection is link dependent, the CCITT CRC
  1035.    used in [9] strikes an excellent balance between ease of computation and
  1036.    robust error detection for a large variety of links, particularly at the
  1037.    relatively small packet sizes needed for good interactive response.
  1038.    Thus, for the sake of interoperability, the framing in [9] should be
  1039.    used unless there is a truly compelling reason to do otherwise.
  1040.  
  1041.  
  1042.    Jacobson                                                       [Page 15]
  1043.  
  1044.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1045.  
  1046.  
  1047.    packet, packet two, and generates an incorrect sequence number for
  1048.    packet four.  After the error, all reconstructed packets' sequence
  1049.    numbers will be in error, shifted down by the amount of data in the
  1050.    missing packet./28/
  1051.  
  1052.    Without some sort of check, the preceding error would result in the
  1053.    receiver invisibly losing two bytes from the middle of the transfer
  1054.    (since the decompressor regenerates sequence numbers, the packets
  1055.    containing F and GH arrive at the receiver's TCP with exactly the
  1056.    sequence numbers they would have had if the DE packet had never
  1057.    existed).  Although some TCP conversations can survive missing data/29/
  1058.    it is not a practice to be encouraged.  Fortunately the TCP checksum,
  1059.    since it is a simple sum of the packet contents including the sequence
  1060.    numbers, detects 100% of these errors.  E.g., the receiver's computed
  1061.    checksum for the last two packets above always differs from the packet
  1062.    checksum by two.
  1063.  
  1064.    Unfortunately, there is a way for the TCP checksum protection described
  1065.    above to fail if the changes in an incoming compressed packet are
  1066.    applied to the wrong conversation:  Consider two active conversations C1
  1067.    and C2 and a packet from C1 followed by two packets from C2.  Since the
  1068.    connection number doesn't change, it's omitted from the second C2
  1069.    packet.  But, if the first C2 packet is received with a CRC error, the
  1070.    second C2 packet will mistakenly be considered the next packet in C1.
  1071.    Since the C2 checksum is a random number with respect to the C1 sequence
  1072.    numbers, there is at least a 2^-16 probability that this packet will be
  1073.    accepted by the C1 TCP receiver./30/  To prevent this, after a CRC error
  1074.    indication from the framer the receiver discards packets until it
  1075.    receives either a COMPRESSED_TCP packet with the C bit set or an
  1076.    UNCOMPRESSED_TCP packet.  I.e., packets are discarded until the receiver
  1077.    gets an explicit connection number.
  1078.  
  1079.    To summarize this section, there are two different types of errors:
  1080.    per-packet corruption and per-conversation loss-of-sync.  The first type
  1081.    is detected at the decompressor from a link-level CRC error, the second
  1082.    at the TCP receiver from a (guaranteed) invalid TCP checksum.  The
  1083.    combination of these two independent mechanisms ensures that erroneous
  1084.    packets are discarded.
  1085.  
  1086.  
  1087.  
  1088.  
  1089.  
  1090.    ----------------------------
  1091.     28. This is an example of a generic problem with differential or delta
  1092.    encodings known as `losing DC'.
  1093.     29. Many system managers claim that holes in an NNTP stream are more
  1094.    valuable than the data.
  1095.     30. With worst-case traffic, this probability translates to one
  1096.    undetected error every three hours over a 9600 baud line with a 30%
  1097.    error rate).
  1098.  
  1099.  
  1100.    Jacobson                                                       [Page 16]
  1101.  
  1102.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1103.  
  1104.  
  1105.    4.2  Error recovery
  1106.  
  1107.    The previous section noted that after a CRC error the decompressor will
  1108.    introduce TCP checksum errors in every uncompressed packet.  Although
  1109.    the checksum errors prevent data stream corruption, the TCP conversation
  1110.    won't be terribly useful until the decompressor again generates valid
  1111.    packets.  How can this be forced to happen?
  1112.  
  1113.    The decompressor generates invalid packets because its state (the saved
  1114.    `last packet header') disagrees with the compressor's state.  An
  1115.    UNCOMPRESSED_TCP packet will correct the decompressor's state.  Thus
  1116.    error recovery amounts to forcing an uncompressed packet out of the
  1117.    compressor whenever the decompressor is (or might be) confused.
  1118.  
  1119.    The first thought is to take advantage of the full duplex communication
  1120.    link and have the decompressor send something to the compressor
  1121.    requesting an uncompressed packet.  This is clearly undesirable since it
  1122.    constrains the topology more than the minimum suggested in sec. 2 and
  1123.    requires that a great deal of protocol be added to both the decompressor
  1124.    and compressor.  A little thought convinces one that this alternative is
  1125.    not only undesirable, it simply won't work:  Compressed packets are
  1126.    small and it's likely that a line hit will so completely obliterate one
  1127.    that the decompressor will get nothing at all.  Thus packets are
  1128.    reconstructed incorrectly (because of the missing compressed packet) but
  1129.    only the TCP end points, not the decompressor, know that the packets are
  1130.    incorrect.
  1131.  
  1132.    But the TCP end points know about the error and TCP is a reliable
  1133.    protocol designed to run over unreliable media.  This means the end
  1134.    points must eventually take some sort of error recovery action and
  1135.    there's an obvious trigger for the compressor to resync the
  1136.    decompressor:  send uncompressed packets whenever TCP is doing error
  1137.    recovery.
  1138.  
  1139.    But how does the compressor recognize TCP error recovery?  Consider the
  1140.    schematic TCP data transfer of fig. 6.    The confused decompressor is
  1141.    in the forward (data transfer) half of the TCP conversation.  The
  1142.    receiving TCP discards packets rather than acking them (because of the
  1143.    checksum errors), the sending TCP eventually times out and retransmits a
  1144.    packet, and the forward path compressor finds that the difference
  1145.    between the sequence number in the retransmitted packet and the sequence
  1146.    number in the last packet seen is either negative (if there were
  1147.    multiple packets in transit) or zero (one packet in transit).  The first
  1148.    case is detected in the compression step that computes sequence number
  1149.    differences.  The second case is detected in the step that checks the
  1150.    `special case' encodings but needs an additional test:  It's fairly
  1151.    common for an interactive conversation to send a dataless ack packet
  1152.    followed by a data packet.  The ack and data packet will have the same
  1153.    sequence numbers yet the data packet is not a retransmission.  To
  1154.    prevent sending an unnecessary uncompressed packet, the length of the
  1155.    previous packet should be checked and, if it contained data, a zero
  1156.  
  1157.  
  1158.    Jacobson                                                       [Page 17]
  1159.  
  1160.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1161.  
  1162.  
  1163.    sequence number change must indicate a retransmission.
  1164.  
  1165.    A confused decompressor in the reverse (ack) half of the conversation is
  1166.    as easy to detect (fig. 7):    The sending TCP discards acks (because
  1167.    they contain checksum errors), eventually times out, then retransmits
  1168.    some packet.  The receiving TCP thus gets a duplicate packet and must
  1169.    generate an ack for the next expected sequence number[11, p. 69].  This
  1170.    ack will be a duplicate of the last ack the receiver generated so the
  1171.    reverse-path compressor will find no ack, seq number, window or urg
  1172.    change.  If this happens for a packet that contains no data, the
  1173.    compressor assumes it is a duplicate ack sent in response to a
  1174.    retransmit and sends an UNCOMPRESSED_TCP packet./31/
  1175.  
  1176.  
  1177.  
  1178.    5  Configurable parameters and tuning
  1179.  
  1180.  
  1181.    5.1  Compression configuration
  1182.  
  1183.    There are two configuration parameters associated with header
  1184.    compression:  Whether or not compressed packets should be sent on a
  1185.    particular line and, if so, how many state slots (saved packet headers)
  1186.    to reserve.  There is also one link-level configuration parameter, the
  1187.    maximum packet size or MTU, and one front-end configuration parameter,
  1188.    data compression, that interact with header compression.  Compression
  1189.    configuration is discussed in this section.  MTU and data compression
  1190.    are discussed in the next two sections.
  1191.  
  1192.    There are some hosts (e.g., low end PCs) which may not have enough
  1193.    processor or memory resources to implement this compression.  There are
  1194.    also rare link or application characteristics that make header
  1195.    compression unnecessary or undesirable.  And there are many existing
  1196.    SLIP links that do not currently use this style of header compression.
  1197.    For the sake of interoperability, serial line IP drivers that allow
  1198.    header compression should include some sort of user configurable flag to
  1199.    disable compression (see appendix B.2)./32/
  1200.  
  1201.    If compression is enabled, the compressor must be sure to never send a
  1202.    connection id (state index) that will be dropped by the decompressor.
  1203.    E.g., a black hole is created if the decompressor has sixteen slots and
  1204.  
  1205.    ----------------------------
  1206.     31. The packet could be a zero-window probe rather than a retransmitted
  1207.    ack but window probes should be infrequent and it does no harm to send
  1208.    them uncompressed.
  1209.     32. The PPP protocol in [9] allows the end points to negotiate
  1210.    compression so there is no interoperability problem.  However, there
  1211.    should still be a provision for the system manager at each end to
  1212.    control whether compression is negotiated on or off.  And, obviously,
  1213.    compression should default to `off' until it has been negotiated `on'.
  1214.  
  1215.  
  1216.    Jacobson                                                       [Page 18]
  1217.  
  1218.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1219.  
  1220.  
  1221.    the compressor uses twenty./33/  Also, if the compressor is allowed too
  1222.    few slots, the LRU allocator will thrash and most packets will be sent
  1223.    as UNCOMPRESSED_TCP. Too many slots and memory is wasted.
  1224.  
  1225.    Experimenting with different sizes over the past year, the author has
  1226.    found that eight slots will thrash (i.e., the performance degradation is
  1227.    noticeable) when many windows on a multi-window workstation are
  1228.    simultaneously in use or the workstation is being used as a gateway for
  1229.    three or more other machines.  Sixteen slots were never observed to
  1230.    thrash.  (This may simply be because a 9600 bps line split more than 16
  1231.    ways is already so overloaded that the additional degradation from
  1232.    round-robbining slots is negligible.)
  1233.  
  1234.    Each slot must be large enough to hold a maximum length TCP/IP header of
  1235.    128 bytes/34/ so 16 slots occupy 2KB of memory.  In these days of 4 Mbit
  1236.    RAM chips, 2KB seems so little memory that the author recommends the
  1237.    following configuration rules:
  1238.  
  1239.    (1) If the framing protocol does not allow negotiation, the compressor
  1240.        and decompressor should provide sixteen slots, zero through fifteen.
  1241.  
  1242.    (2) If the framing protocol allows negotiation, any mutually agreeable
  1243.        number of slots from 1 to 256 should be negotiable./35/  If number
  1244.        of slots is not negotiated, or until it is negotiated, both sides
  1245.        should assume sixteen.
  1246.  
  1247.    (3) If you have complete control of all the machines at both ends of
  1248.        every link and none of them will ever be used to talk to machines
  1249.        outside of your control, you are free to configure them however you
  1250.        please, ignoring the above.  However, when your little eastern-block
  1251.        dictatorship collapses (as they all eventually seem to), be aware
  1252.        that a large, vocal, and not particularly forgiving Internet
  1253.        community will take great delight in pointing out to anyone willing
  1254.  
  1255.  
  1256.    ----------------------------
  1257.     33. Strictly speaking, there's no reason why the connection id should
  1258.    be treated as an array index.  If the decompressor's states were kept in
  1259.    a hash table or other associative structure, the connection id would be
  1260.    a key, not an index, and performance with too few decompressor slots
  1261.    would only degrade enormously rather than failing altogether.  However,
  1262.    an associative structure is substantially more costly in code and cpu
  1263.    time and, given the small per-slot cost (128 bytes of memory), it seems
  1264.    reasonable to design for slot arrays at the decompressor and some
  1265.    (possibly implicit) communication of the array size.
  1266.     34. The maximum header length, fixed by the protocol design, is 64
  1267.    bytes of IP and 64 bytes of TCP.
  1268.     35. Allowing only one slot may make the compressor code more complex.
  1269.    Implementations should avoid offering one slot if possible and
  1270.    compressor implementations may disable compression if only one slot is
  1271.    negotiated.
  1272.  
  1273.  
  1274.    Jacobson                                                       [Page 19]
  1275.  
  1276.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1277.  
  1278.  
  1279.        to listen that you have misconfigured your systems and are not
  1280.        interoperable.
  1281.  
  1282.  
  1283.    5.2  Choosing a maximum transmission unit
  1284.  
  1285.    From the discussion in sec. 2, it seems desirable to limit the maximum
  1286.    packet size (MTU) on any line where there might be interactive traffic
  1287.    and multiple active connections (to maintain good interactive response
  1288.    between the different connections competing for the line).  The obvious
  1289.    question is `how much does this hurt throughput?'  It doesn't.
  1290.  
  1291.    Figure 8 shows how user data throughput/36/ scales with MTU with (solid
  1292.    line) and without (dashed line) header compression.  The dotted lines
  1293.    show what MTU corresponds to a 200 ms packet time at 2400, 9600 and
  1294.    19,200 bps.  Note that with header compression even a 2400 bps line can
  1295.    be responsive yet have reasonable throughput (83%)./37/
  1296.  
  1297.    Figure 9 shows how line efficiency scales with increasing line speed,
  1298.    assuming that a 200ms. MTU is always chosen./38/  The knee in the
  1299.    performance curve is around 2400 bps.  Below this, efficiency is
  1300.    sensitive to small changes in speed (or MTU since the two are linearly
  1301.    related) and good efficiency comes at the expense of good response.
  1302.    Above 2400bps the curve is flat and efficiency is relatively independent
  1303.    of speed or MTU. In other words, it is possible to have both good
  1304.    response and high line efficiency.
  1305.  
  1306.    To illustrate, note that for a 9600 bps line with header compression
  1307.    there is essentially no benefit in increasing the MTU beyond 200 bytes:
  1308.    If the MTU is increased to 576, the average delay increases by 188%
  1309.    while throughput only improves by 3% (from 96 to 99%).
  1310.  
  1311.  
  1312.  
  1313.  
  1314.  
  1315.  
  1316.  
  1317.    ----------------------------
  1318.     36. The vertical axis is in percent of line speed.  E.g., `95' means
  1319.    that 95% of the line bandwidth is going to user data or, in other words,
  1320.    the user would see a data transfer rate of 9120 bps on a 9600 bps line.
  1321.    Four bytes of link-level (framer) encapsulation in addition to the
  1322.    TCP/IP or compressed header were included when calculating the relative
  1323.    throughput.  The 200 ms packet times were computed assuming an
  1324.    asynchronous line using 10 bits per character (8 data bits, 1 start, 1
  1325.    stop, no parity).
  1326.     37. However, the 40 byte TCP MSS required for a 2400 bps line might
  1327.    stress-test your TCP implementation.
  1328.     38. For a typical async line, a 200ms. MTU is simply .02 times the line
  1329.    speed in bits per second.
  1330.  
  1331.  
  1332.    Jacobson                                                       [Page 20]
  1333.  
  1334.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1335.  
  1336.  
  1337.    5.3  Interaction with data compression
  1338.  
  1339.    Since the early 1980's, fast, effective, data compression algorithms
  1340.    such as Lempel-Ziv[7] and programs that embody them, such as the
  1341.    compress program shipped with Berkeley Unix, have become widely
  1342.    available.  When using low speed or long haul lines, it has become
  1343.    common practice to compress data before sending it.  For dialup
  1344.    connections, this compression is often done in the modems, independent
  1345.    of the communicating hosts.  Some interesting issues would seem to be:
  1346.    (1) Given a good data compressor, is there any need for header
  1347.    compression?  (2) Does header compression interact with data
  1348.    compression?  (3) Should data be compressed before or after header
  1349.    compression?/39/
  1350.  
  1351.    To investigate (1), Lempel-Ziv compression was done on a trace of 446
  1352.    TCP/IP packets taken from the user's side of a typical telnet
  1353.    conversation.  Since the packets resulted from typing, almost all
  1354.    contained only one data byte plus 40 bytes of header.  I.e., the test
  1355.    essentially measured L-Z compression of TCP/IP headers.  The compression
  1356.    ratio (the ratio of uncompressed to compressed data) was 2.6.  In other
  1357.    words, the average header was reduced from 40 to 16 bytes.  While this
  1358.    is good compression, it is far from the 5 bytes of header needed for
  1359.    good interactive response and far from the 3 bytes of header (a
  1360.    compression ratio of 13.3) that header compression yielded on the same
  1361.    packet trace.
  1362.  
  1363.    The second and third questions are more complex.  To investigate them,
  1364.    several packet traces from FTP file transfers were analyzed/40/ with and
  1365.    without header compression and with and without L-Z compression.  The
  1366.    L-Z compression was tried at two places in the outgoing data stream
  1367.    (fig. 10):    (1) just before the data was handed to TCP for
  1368.    encapsulation (simulating compression done at the `application' level)
  1369.    and (2) after the data was encapsulated (simulating compression done in
  1370.    the modem).  Table 1 summarizes the results for a 78,776 byte ASCII text
  1371.    file (the Unix csh.1 manual entry)/41/ transferred using the guidelines
  1372.    of the previous section (256 byte MTU or 216 byte MSS; 368 packets
  1373.    total).  Compression ratios for the following ten tests are shown
  1374.    (reading left to right and top to bottom):
  1375.  
  1376.    ----------------------------
  1377.     39. The answers, for those who wish to skip the remainder of this
  1378.    section, are `yes', `no' and `either', respectively.
  1379.     40. The data volume from user side of a telnet is too small to benefit
  1380.    from data compression and can be adversely affected by the delay most
  1381.    compression algorithms (necessarily) add.  The statistics and volume of
  1382.    the computer side of a telnet are similar to an (ASCII) FTP so these
  1383.    results should apply to either.
  1384.     41. The ten experiments described were each done on ten ASCII files
  1385.    (four long e-mail messages, three Unix C source files and three Unix
  1386.    manual entries).  The results were remarkably similar for different
  1387.    files and the general conclusions reached below apply to all ten files.
  1388.  
  1389.  
  1390.    Jacobson                                                       [Page 21]
  1391.  
  1392.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1393.  
  1394.  
  1395.      - data file (no compression or encapsulation)
  1396.  
  1397.      - data -> L--Z compressor
  1398.  
  1399.      - data -> TCP/IP encapsulation
  1400.  
  1401.      - data -> L--Z -> TCP/IP
  1402.  
  1403.      - data -> TCP/IP -> L--Z
  1404.  
  1405.      - data -> L--Z -> TCP/IP -> L--Z
  1406.  
  1407.      - data -> TCP/IP -> Hdr. Compress.
  1408.  
  1409.      - data -> L--Z -> TCP/IP -> Hdr. Compress.
  1410.  
  1411.      - data -> TCP/IP -> Hdr. Compress. -> L--Z
  1412.  
  1413.      - data -> L--Z -> TCP/IP -> Hdr. Compress. -> L--Z
  1414.  
  1415.  
  1416.             +-----------------------------------------------------+
  1417.             |              | No data  | L--Z   |  L--Z  |  L--Z   |
  1418.             |              |compress. |on data |on wire | on both |
  1419.             +--------------+----------+--------+--------+---------+
  1420.             | Raw Data     |     1.00 |   2.44 |   ---- |    ---- |
  1421.             | + TCP Encap. |     0.83 |   2.03 |   1.97 |    1.58 |
  1422.             | w/Hdr Comp.  |     0.98 |   2.39 |   2.26 |    1.66 |
  1423.             +-----------------------------------------------------+
  1424.  
  1425.                  Table 1:  ASCII Text File Compression Ratios
  1426.  
  1427.  
  1428.    The first column of table 1 says the data expands by 19% (`compresses'
  1429.    by .83) when encapsulated in TCP/IP and by 2% when encapsulated in
  1430.    header compressed TCP/IP./42/ The first row says L--Z compression is
  1431.    quite effective on this data, shrinking it to less than half its
  1432.    original size.  Column four illustrates the well-known fact that it is a
  1433.    mistake to L--Z compress already compressed data.  The interesting
  1434.    information is in rows two and three of columns two and three.  These
  1435.    columns say that the benefit of data compression overwhelms the cost of
  1436.    encapsulation, even for straight TCP/IP. They also say that it is
  1437.    slightly better to compress the data before encapsulating it rather than
  1438.    compressing at the framing/modem level.  The differences however are
  1439.  
  1440.  
  1441.  
  1442.  
  1443.    ----------------------------
  1444.     42. This is what would be expected from the relative header sizes:
  1445.    256/216 for TCP/IP and 219/216 for header compression.
  1446.  
  1447.  
  1448.    Jacobson                                                       [Page 22]
  1449.  
  1450.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1451.  
  1452.  
  1453.    small --- 3% and 6%, respectively, for the TCP/IP and header compressed
  1454.    encapsulations./43/
  1455.  
  1456.    Table 2 shows the same experiment for a 122,880 byte binary file (the
  1457.    Sun-3 ps executable).  Although the raw data doesn't compress nearly as
  1458.    well, the results are qualitatively the same as for the ASCII data.  The
  1459.    one significant change is in row two:  It is about 3% better to compress
  1460.    the data in the modem rather than at the source if doing TCP/IP
  1461.    encapsulation (apparently, Sun binaries and TCP/IP headers have similar
  1462.    statistics).  However, with header compression (row three) the results
  1463.    were similar to the ASCII data --- it's about 3% worse to compress at
  1464.    the modem rather than the source./44/
  1465.  
  1466.  
  1467.             +-----------------------------------------------------+
  1468.             |              | No data  | L--Z   |  L--Z  |  L--Z   |
  1469.             |              |compress. |on data |on wire | on both |
  1470.             +--------------+----------+--------+--------+---------+
  1471.             | Raw Data     |     1.00 |   1.72 |   ---- |    ---- |
  1472.             | + TCP Encap. |     0.83 |   1.43 |   1.48 |    1.21 |
  1473.             | w/Hdr Comp.  |     0.98 |   1.69 |   1.64 |    1.28 |
  1474.             +-----------------------------------------------------+
  1475.  
  1476.                    Table 2:  Binary File Compression Ratios
  1477.  
  1478.  
  1479.  
  1480.  
  1481.    6  Performance measurements
  1482.  
  1483.  
  1484.    An implementation goal of compression code was to arrive at something
  1485.    simple enough to run at ISDN speeds (64Kbps) on a typical 1989
  1486.  
  1487.  
  1488.  
  1489.    ----------------------------
  1490.     43. The differences are due to the wildly different byte patterns of
  1491.    TCP/IP datagrams and ASCII text.  Any compression scheme with an
  1492.    underlying, Markov source model, such as Lempel-Ziv, will do worse when
  1493.    radically different sources are interleaved.  If the relative
  1494.    proportions of the two sources are changed, i.e., the MTU is increased,
  1495.    the performance difference between the two compressor locations
  1496.    decreases.  However, the rate of decrease is very slow --- increasing
  1497.    the MTU by 400% (256 to 1024) only changed the difference between the
  1498.    data and modem L--Z choices from 2.5% to 1.3%.
  1499.     44. There are other good reasons to compress at the source:  Far fewer
  1500.    packets have to be encapsulated and far fewer characters have to be sent
  1501.    to the modem.  The author suspects that the `compress data in the modem'
  1502.    alternative should be avoided except when faced with an intractable,
  1503.    vendor proprietary operating system.
  1504.  
  1505.  
  1506.    Jacobson                                                       [Page 23]
  1507.  
  1508.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1509.  
  1510.  
  1511.  
  1512.                    +---------------------------------------+
  1513.                    |               |  Average per-packet   |
  1514.                    |    Machine    | processing time (us.) |
  1515.                    |               |                       |
  1516.                    |               | Compress | Decompress |
  1517.                    +---------------+----------+------------+
  1518.                    |Sparcstation-1 |       24 |         18 |
  1519.                    |   Sun 4/260   |       46 |         20 |
  1520.                    |   Sun 3/60    |       90 |         90 |
  1521.                    |   Sun 3/50    |      130 |        150 |
  1522.                    |  HP9000/370   |       42 |         33 |
  1523.                    |  HP9000/360   |       68 |         70 |
  1524.                    |   DEC 3100    |       27 |         25 |
  1525.                    |    Vax 780    |      430 |        300 |
  1526.                    |    Vax 750    |      800 |        500 |
  1527.                    |   CCI Tahoe   |      110 |        140 |
  1528.                    +---------------------------------------+
  1529.  
  1530.                       Table 3:  Compression code timings
  1531.  
  1532.  
  1533.    workstation.  64Kbps is a byte every 122us so 120us was (arbitrarily)
  1534.    picked as the target compression/decompression time./45/
  1535.  
  1536.    As part of the compression code development, a trace-driven exerciser
  1537.    was developed.  This was initially used to compare different compression
  1538.    protocol choices then later to test the code on different computer
  1539.    architectures and do regression tests after performance `improvements'.
  1540.    A small modification of this test program resulted in a useful
  1541.    measurement tool./46/  Table 3 shows the result of timing the
  1542.    compression code on all the machines available to the author (times were
  1543.    measured using a mixed telnet/ftp traffic trace).  With the exception of
  1544.    the Vax architectures, which suffer from (a) having bytes in the wrong
  1545.    order and (b) a lousy compiler (Unix pcc), all machines essentially met
  1546.    the 120us goal.
  1547.  
  1548.  
  1549.  
  1550.  
  1551.    ----------------------------
  1552.     45. The time choice wasn't completely arbitrary:  Decompression is
  1553.    often done during the inter-frame `flag' character time so, on systems
  1554.    where the decompression is done at the same priority level as the serial
  1555.    line input interrupt, times much longer than a character time would
  1556.    result in receiver overruns.  And, with the current average of five byte
  1557.    frames (on the wire, including both compressed header and framing), a
  1558.    compression/decompression that takes one byte time can use at most 20%
  1559.    of the available time.  This seems like a comfortable budget.
  1560.     46. Both the test program and timer program are included in the
  1561.    ftp-able package described in appendix A as files tester.c and timer.c.
  1562.  
  1563.  
  1564.    Jacobson                                                       [Page 24]
  1565.  
  1566.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1567.  
  1568.  
  1569.    7  Acknowlegements
  1570.  
  1571.  
  1572.    The author is grateful to the members of the Internet Engineering Task
  1573.    Force, chaired by Phill Gross, who provided encouragement and thoughtful
  1574.    review of this work.  Several patient beta-testers, particularly Sam
  1575.    Leffler and Craig Leres, tracked down and fixed problems in the initial
  1576.    implementation.  Cynthia Livingston and Craig Partridge carefully read
  1577.    and greatly improved an unending sequence of partial drafts of this
  1578.    document.  And last but not least, Telebit modem corporation,
  1579.    particularly Mike Ballard, encouraged this work from its inception and
  1580.    has been an ongoing champion of serial line and dial-up IP.
  1581.  
  1582.  
  1583.    References
  1584.  
  1585.     [1] Bingham, J. A. C. Theory and Practice of Modem Design. John Wiley
  1586.         & Sons, 1988.
  1587.  
  1588.     [2] Carey, M. B., Chan, H.-T., Descloux, A., Ingle, J. F., and Park,
  1589.         K. I. 1982/83 end office connection study:  Analog voice and
  1590.         voiceband data transmission performance characterization of the
  1591.         public switched network. Bell System Technical Journal 63, 9 (Nov.
  1592.         1984).
  1593.  
  1594.     [3] Chiappa, N., 1988. Private communication.
  1595.  
  1596.     [4] Clark, D. D. The design philosophy of the DARPA Internet
  1597.         protocols. In Proceedings of SIGCOMM '88 (Stanford, CA, Aug.
  1598.         1988), ACM.
  1599.  
  1600.     [5] Farber, D. J., Delp, G. S., and Conte, T. M. A Thinwire Protocol
  1601.         for connecting personal computers to the Internet. Arpanet Working
  1602.         Group Requests for Comment, DDN Network Information Center, SRI
  1603.         International, Menlo Park, CA, Sept. 1984. RFC-914.
  1604.  
  1605.     [6] Kent, C. A., and Mogul, J. Fragmentation considered harmful. In
  1606.         Proceedings of SIGCOMM '87 (Aug. 1987), ACM.
  1607.  
  1608.     [7] Lempel, A., and Ziv, J. Compression of individual sequences via
  1609.         variable-rate encoding. IEEE Transactions on Information Theory
  1610.         IT-24, 5 (June 1978).
  1611.  
  1612.     [8] Nagle, J. Congestion Control in IP/TCP Internetworks. Arpanet
  1613.         Working Group Requests for Comment, DDN Network Information Center,
  1614.         SRI International, Menlo Park, CA, Jan. 1984. RFC-896.
  1615.  
  1616.     [9] Perkins, D. Point-to-Point Protocol:  A proposal for
  1617.         multi-protocol transmission of datagrams over point-to-point links.
  1618.         Arpanet Working Group Requests for Comment, DDN Network Information
  1619.         Center, SRI International, Menlo Park, CA, Nov. 1989. RFC-1134.
  1620.  
  1621.  
  1622.    Jacobson                                                       [Page 25]
  1623.  
  1624.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1625.  
  1626.  
  1627.    [10] Postel, J., Ed. Internet Protocol Specification. SRI
  1628.         International, Menlo Park, CA, Sept. 1981. RFC-791.
  1629.  
  1630.    [11] Postel, J., Ed. Transmission Control Protocol Specification. SRI
  1631.         International, Menlo Park, CA, Sept. 1981. RFC-793.
  1632.  
  1633.    [12] Romkey, J. A Nonstandard for Transmission of IP Datagrams Over
  1634.         Serial Lines:  Slip. Arpanet Working Group Requests for Comment,
  1635.         DDN Network Information Center, SRI International, Menlo Park, CA,
  1636.         June 1988. RFC-1055.
  1637.  
  1638.    [13] Salthouse, T. A. The skill of typing. Scientific American 250, 2
  1639.         (Feb. 1984), 128--135.
  1640.  
  1641.    [14] Saltzer, J. H., Reed, D. P., and Clark, D. D. End-to-end arguments
  1642.         in system design. ACM Transactions on Computer Systems 2, 4 (Nov.
  1643.         1984).
  1644.  
  1645.    [15] Shneiderman, B. Designing the User Interface. Addison-Wesley,
  1646.         1987.
  1647.  
  1648.  
  1649.  
  1650.  
  1651.  
  1652.  
  1653.  
  1654.  
  1655.  
  1656.  
  1657.  
  1658.  
  1659.  
  1660.  
  1661.  
  1662.  
  1663.  
  1664.  
  1665.  
  1666.  
  1667.  
  1668.  
  1669.  
  1670.  
  1671.  
  1672.  
  1673.  
  1674.  
  1675.  
  1676.  
  1677.  
  1678.  
  1679.  
  1680.    Jacobson                                                       [Page 26]
  1681.  
  1682.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1683.  
  1684.  
  1685.    A  Sample Implementation
  1686.  
  1687.  
  1688.    The following is a sample implementation of the protocol described in
  1689.    this document.
  1690.  
  1691.    Since many people who might have the deal with this code are familiar
  1692.    with the Berkeley Unix kernel and its coding style (affectionately known
  1693.    as kernel normal form), this code was done in that style.  It uses the
  1694.    Berkeley `subroutines' (actually, macros and/or inline assembler
  1695.    expansions) for converting to/from network byte order and
  1696.    copying/comparing strings of bytes.  These routines are briefly
  1697.    described in sec. A.5 for anyone not familiar with them.
  1698.  
  1699.    This code has been run on all the machines listed in the table on page
  1700.    24.  Thus, the author hopes there are no byte order or alignment
  1701.    problems (although there are embedded assumptions about alignment that
  1702.    are valid for Berkeley Unix but may not be true for other IP
  1703.    implementations --- see the comments mentioning alignment in
  1704.    sl_compress_tcp and sl_decompress_tcp).
  1705.  
  1706.    There was some attempt to make this code efficient.  Unfortunately, that
  1707.    may have made portions of it incomprehensible.  The author apologizes
  1708.    for any frustration this engenders.  (In honesty, my C style is known to
  1709.    be obscure and claims of `efficiency' are simply a convenient excuse.)
  1710.  
  1711.    This sample code and a complete Berkeley Unix implementation is
  1712.    available in machine readable form via anonymous ftp from Internet host
  1713.    ftp.ee.lbl.gov (128.3.254.68), file cslip.tar.Z. This is a compressed
  1714.    Unix tar file.  It must be ftped in binary mode.
  1715.  
  1716.    All of the code in this appendix is covered by the following copyright:
  1717.  
  1718.    /*
  1719.     * Copyright (c) 1989 Regents of the University of California.
  1720.     * All rights reserved.
  1721.     *
  1722.     * Redistribution and use in source and binary forms are
  1723.     * permitted provided that the above copyright notice and this
  1724.     * paragraph are duplicated in all such forms and that any
  1725.     * documentation, advertising materials, and other materials
  1726.     * related to such distribution and use acknowledge that the
  1727.     * software was developed by the University of California,
  1728.     * Berkeley.  The name of the University may not be used to
  1729.     * endorse or promote products derived from this software
  1730.     * without specific prior written permission.
  1731.     * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS
  1732.     * OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE
  1733.     * IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A
  1734.     * PARTICULAR PURPOSE.
  1735.     */
  1736.  
  1737.  
  1738.    Jacobson                                                       [Page 27]
  1739.  
  1740.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1741.  
  1742.  
  1743.    A.1  Definitions and State Data
  1744.  
  1745.    #define MAX_STATES 16   /* must be >2 and <255 */
  1746.    #define MAX_HDR 128     /* max TCP+IP hdr length (by protocol def) */
  1747.  
  1748.    /* packet types */
  1749.    #define TYPE_IP 0x40
  1750.    #define TYPE_UNCOMPRESSED_TCP 0x70
  1751.    #define TYPE_COMPRESSED_TCP 0x80
  1752.    #define TYPE_ERROR 0x00 /* this is not a type that ever appears on
  1753.                             * the wire.  The receive framer uses it to
  1754.                             * tell the decompressor there was a packet
  1755.                             * transmission error. */
  1756.    /*
  1757.     * Bits in first octet of compressed packet
  1758.     */
  1759.  
  1760.    /* flag bits for what changed in a packet */
  1761.  
  1762.    #define NEW_C  0x40
  1763.    #define NEW_I  0x20
  1764.    #define TCP_PUSH_BIT 0x10
  1765.  
  1766.    #define NEW_S  0x08
  1767.    #define NEW_A  0x04
  1768.    #define NEW_W  0x02
  1769.    #define NEW_U  0x01
  1770.  
  1771.    /* reserved, special-case values of above */
  1772.    #define SPECIAL_I (NEW_S|NEW_W|NEW_U)        /* echoed interactive traffic */
  1773.    #define SPECIAL_D (NEW_S|NEW_A|NEW_W|NEW_U)  /* unidirectional data */
  1774.    #define SPECIALS_MASK (NEW_S|NEW_A|NEW_W|NEW_U)
  1775.  
  1776.  
  1777.    /*
  1778.     * "state" data for each active tcp conversation on the wire.  This is
  1779.     * basically a copy of the entire IP/TCP header from the last packet together
  1780.     * with a small identifier the transmit & receive ends of the line use to
  1781.     * locate saved header.
  1782.     */
  1783.    struct cstate {
  1784.         struct cstate *cs_next;  /* next most recently used cstate (xmit only) */
  1785.         u_short cs_hlen;         /* size of hdr (receive only) */
  1786.         u_char cs_id;            /* connection # associated with this state */
  1787.         u_char cs_filler;
  1788.         union {
  1789.              char hdr[MAX_HDR];
  1790.              struct ip csu_ip;   /* ip/tcp hdr from most recent packet */
  1791.         } slcs_u;
  1792.    };
  1793.    #define cs_ip slcs_u.csu_ip
  1794.  
  1795.  
  1796.    Jacobson                                                       [Page 28]
  1797.  
  1798.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1799.  
  1800.  
  1801.    #define cs_hdr slcs_u.csu_hdr
  1802.  
  1803.    /*
  1804.     * all the state data for one serial line (we need one of these per line).
  1805.     */
  1806.    struct slcompress {
  1807.         struct cstate *last_cs;            /* most recently used tstate */
  1808.         u_char last_recv;                  /* last rcvd conn. id */
  1809.         u_char last_xmit;                  /* last sent conn. id */
  1810.         u_short flags;
  1811.         struct cstate tstate[MAX_STATES];  /* xmit connection states */
  1812.         struct cstate rstate[MAX_STATES];  /* receive connection states */
  1813.    };
  1814.  
  1815.    /* flag values */
  1816.    #define SLF_TOSS 1       /* tossing rcvd frames because of input err */
  1817.  
  1818.    /*
  1819.     * The following macros are used to encode and decode numbers.  They all
  1820.     * assume that `cp' points to a buffer where the next byte encoded (decoded)
  1821.     * is to be stored (retrieved).  Since the decode routines do arithmetic,
  1822.     * they have to convert from and to network byte order.
  1823.     */
  1824.  
  1825.    /*
  1826.     * ENCODE encodes a number that is known to be non-zero.  ENCODEZ checks for
  1827.     * zero (zero has to be encoded in the long, 3 byte form).
  1828.     */
  1829.    #define ENCODE(n) { \
  1830.         if ((u_short)(n) >= 256) { \
  1831.              *cp++ = 0; \
  1832.              cp[1] = (n); \
  1833.              cp[0] = (n) >> 8; \
  1834.              cp += 2; \
  1835.         } else { \
  1836.              *cp++ = (n); \
  1837.         } \
  1838.    }
  1839.    #define ENCODEZ(n) { \
  1840.         if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \
  1841.              *cp++ = 0; \
  1842.              cp[1] = (n); \
  1843.              cp[0] = (n) >> 8; \
  1844.              cp += 2; \
  1845.         } else { \
  1846.              *cp++ = (n); \
  1847.         } \
  1848.    }
  1849.  
  1850.    /*
  1851.     * DECODEL takes the (compressed) change at byte cp and adds it to the
  1852.  
  1853.  
  1854.    Jacobson                                                       [Page 29]
  1855.  
  1856.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1857.  
  1858.  
  1859.     * current value of packet field 'f' (which must be a 4-byte (long) integer
  1860.     * in network byte order).  DECODES does the same for a 2-byte (short) field.
  1861.     * DECODEU takes the change at cp and stuffs it into the (short) field f.
  1862.     * 'cp' is updated to point to the next field in the compressed header.
  1863.     */
  1864.    #define DECODEL(f) { \
  1865.         if (*cp == 0) {\
  1866.              (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \
  1867.              cp += 3; \
  1868.         } else { \
  1869.              (f) = htonl(ntohl(f) + (u_long)*cp++); \
  1870.         } \
  1871.    }
  1872.    #define DECODES(f) { \
  1873.         if (*cp == 0) {\
  1874.              (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \
  1875.              cp += 3; \
  1876.         } else { \
  1877.              (f) = htons(ntohs(f) + (u_long)*cp++); \
  1878.         } \
  1879.    }
  1880.    #define DECODEU(f) { \
  1881.         if (*cp == 0) {\
  1882.              (f) = htons((cp[1] << 8) | cp[2]); \
  1883.              cp += 3; \
  1884.         } else { \
  1885.              (f) = htons((u_long)*cp++); \
  1886.         } \
  1887.    }
  1888.  
  1889.  
  1890.  
  1891.  
  1892.  
  1893.  
  1894.  
  1895.  
  1896.  
  1897.  
  1898.  
  1899.  
  1900.  
  1901.  
  1902.  
  1903.  
  1904.  
  1905.  
  1906.  
  1907.  
  1908.  
  1909.  
  1910.  
  1911.  
  1912.    Jacobson                                                       [Page 30]
  1913.  
  1914.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1915.  
  1916.  
  1917.    A.2  Compression
  1918.  
  1919.    This routine looks daunting but isn't really.  The code splits into four
  1920.    approximately equal sized sections:  The first quarter manages a
  1921.    circularly linked, least-recently-used list of `active' TCP
  1922.    connections./47/  The second figures out the sequence/ack/window/urg
  1923.    changes and builds the bulk of the compressed packet.  The third handles
  1924.    the special-case encodings.  The last quarter does packet ID and
  1925.    connection ID encoding and replaces the original packet header with the
  1926.    compressed header.
  1927.  
  1928.    The arguments to this routine are a pointer to a packet to be
  1929.    compressed, a pointer to the compression state data for the serial line,
  1930.    and a flag which enables or disables connection id (C bit) compression.
  1931.  
  1932.    Compression is done `in-place' so, if a compressed packet is created,
  1933.    both the start address and length of the incoming packet (the off and
  1934.    len fields of m) will be updated to reflect the removal of the original
  1935.    header and its replacement by the compressed header.  If either a
  1936.    compressed or uncompressed packet is created, the compression state is
  1937.    updated.  This routines returns the packet type for the transmit framer
  1938.    (TYPE_IP, TYPE_UNCOMPRESSED_TCP or TYPE_COMPRESSED_TCP).
  1939.  
  1940.    Because 16 and 32 bit arithmetic is done on various header fields, the
  1941.    incoming IP packet must be aligned appropriately (e.g., on a SPARC, the
  1942.    IP header is aligned on a 32-bit boundary).  Substantial changes would
  1943.    have to be made to the code below if this were not true (and it would
  1944.    probably be cheaper to byte copy the incoming header to somewhere
  1945.    correctly aligned than to make those changes).
  1946.  
  1947.    Note that the outgoing packet will be aligned arbitrarily (e.g., it
  1948.    could easily start on an odd-byte boundary).
  1949.  
  1950.    u_char
  1951.    sl_compress_tcp(m, comp, compress_cid)
  1952.         struct mbuf *m;
  1953.         struct slcompress *comp;
  1954.         int compress_cid;
  1955.    {
  1956.         register struct cstate *cs = comp->last_cs->cs_next;
  1957.         register struct ip *ip = mtod(m, struct ip *);
  1958.         register u_int hlen = ip->ip_hl;
  1959.         register struct tcphdr *oth;       /* last TCP header */
  1960.         register struct tcphdr *th;        /* current TCP header */
  1961.  
  1962.    ----------------------------
  1963.     47. The two most common operations on the connection list are a `find'
  1964.    that terminates at the first entry (a new packet for the most recently
  1965.    used connection) and moving the last entry on the list to the head of
  1966.    the list (the first packet from a new connection).  A circular list
  1967.    efficiently handles these two operations.
  1968.  
  1969.  
  1970.    Jacobson                                                       [Page 31]
  1971.  
  1972.    RFC 1144               Compressing TCP/IP Headers          February 1990
  1973.  
  1974.  
  1975.         register u_int deltaS, deltaA;     /* general purpose temporaries */
  1976.         register u_int changes = 0;        /* change mask */
  1977.         u_char new_seq[16];                /* changes from last to current */
  1978.         register u_char *cp = new_seq;
  1979.  
  1980.         /*
  1981.          * Bail if this is an IP fragment or if the TCP packet isn't
  1982.          * `compressible' (i.e., ACK isn't set or some other control bit is
  1983.          * set).  (We assume that the caller has already made sure the packet
  1984.          * is IP proto TCP).
  1985.          */
  1986.         if ((ip->ip_off & htons(0x3fff)) || m->m_len < 40)
  1987.              return (TYPE_IP);
  1988.  
  1989.         th = (struct tcphdr *) & ((int *) ip)[hlen];
  1990.         if ((th->th_flags & (TH_SYN | TH_FIN | TH_RST | TH_ACK)) != TH_ACK)
  1991.              return (TYPE_IP);
  1992.  
  1993.         /*
  1994.          * Packet is compressible -- we're going to send either a
  1995.          * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way we need to
  1996.          * locate (or create) the connection state.  Special case the most
  1997.          * recently used connection since it's most likely to be used again &
  1998.          * we don't have to do any reordering if it's used.
  1999.          */
  2000.         if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||
  2001.             ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||
  2002.             *(int *) th != ((int *) &cs->cs_ip)[cs->cs_ip.ip_hl]) {
  2003.  
  2004.              /*
  2005.               * Wasn't the first -- search for it.
  2006.               *
  2007.               * States are kept in a circularly linked list with last_cs
  2008.               * pointing to the end of the list.  The list is kept in lru
  2009.               * order by moving a state to the head of the list whenever
  2010.               * it is referenced.  Since the list is short and,
  2011.               * empirically, the connection we want is almost always near
  2012.               * the front, we locate states via linear search.  If we
  2013.               * don't find a state for the datagram, the oldest state is
  2014.               * (re-)used.
  2015.               */
  2016.              register struct cstate *lcs;
  2017.              register struct cstate *lastcs = comp->last_cs;
  2018.  
  2019.              do {
  2020.                   lcs = cs;
  2021.                   cs = cs->cs_next;
  2022.                   if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr
  2023.                       && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr
  2024.                       && *(int *) th == ((int *) &cs->cs_ip)[cs->cs_ip.ip_hl])
  2025.                        goto found;
  2026.  
  2027.  
  2028.    Jacobson                                                       [Page 32]
  2029.  
  2030.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2031.  
  2032.  
  2033.              } while (cs != lastcs);
  2034.  
  2035.              /*
  2036.               * Didn't find it -- re-use oldest cstate.  Send an
  2037.               * uncompressed packet that tells the other side what
  2038.               * connection number we're using for this conversation. Note
  2039.               * that since the state list is circular, the oldest state
  2040.               * points to the newest and we only need to set last_cs to
  2041.               * update the lru linkage.
  2042.               */
  2043.              comp->last_cs = lcs;
  2044.              hlen += th->th_off;
  2045.              hlen <<= 2;
  2046.              goto uncompressed;
  2047.  
  2048.    found:
  2049.              /* Found it -- move to the front on the connection list. */
  2050.              if (lastcs == cs)
  2051.                   comp->last_cs = lcs;
  2052.              else {
  2053.                   lcs->cs_next = cs->cs_next;
  2054.                   cs->cs_next = lastcs->cs_next;
  2055.                   lastcs->cs_next = cs;
  2056.              }
  2057.         }
  2058.         /*
  2059.          * Make sure that only what we expect to change changed. The first
  2060.          * line of the `if' checks the IP protocol version, header length &
  2061.          * type of service.  The 2nd line checks the "Don't fragment" bit.
  2062.          * The 3rd line checks the time-to-live and protocol (the protocol
  2063.          * check is unnecessary but costless).  The 4th line checks the TCP
  2064.          * header length.  The 5th line checks IP options, if any.  The 6th
  2065.          * line checks TCP options, if any.  If any of these things are
  2066.          * different between the previous & current datagram, we send the
  2067.          * current datagram `uncompressed'.
  2068.          */
  2069.         oth = (struct tcphdr *) & ((int *) &cs->cs_ip)[hlen];
  2070.         deltaS = hlen;
  2071.         hlen += th->th_off;
  2072.         hlen <<= 2;
  2073.  
  2074.         if (((u_short *) ip)[0] != ((u_short *) &cs->cs_ip)[0] ||
  2075.             ((u_short *) ip)[3] != ((u_short *) &cs->cs_ip)[3] ||
  2076.             ((u_short *) ip)[4] != ((u_short *) &cs->cs_ip)[4] ||
  2077.             th->th_off != oth->th_off ||
  2078.             (deltaS > 5 && BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||
  2079.             (th->th_off > 5 && BCMP(th + 1, oth + 1, (th->th_off - 5) << 2)))
  2080.              goto uncompressed;
  2081.  
  2082.         /*
  2083.          * Figure out which of the changing fields changed.  The receiver
  2084.  
  2085.  
  2086.    Jacobson                                                       [Page 33]
  2087.  
  2088.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2089.  
  2090.  
  2091.          * expects changes in the order: urgent, window, ack, seq.
  2092.          */
  2093.         if (th->th_flags & TH_URG) {
  2094.              deltaS = ntohs(th->th_urp);
  2095.              ENCODEZ(deltaS);
  2096.              changes |= NEW_U;
  2097.         } else if (th->th_urp != oth->th_urp)
  2098.              /*
  2099.               * argh! URG not set but urp changed -- a sensible
  2100.               * implementation should never do this but RFC793 doesn't
  2101.               * prohibit the change so we have to deal with it.
  2102.               */
  2103.              goto uncompressed;
  2104.  
  2105.         if (deltaS = (u_short) (ntohs(th->th_win) - ntohs(oth->th_win))) {
  2106.              ENCODE(deltaS);
  2107.              changes |= NEW_W;
  2108.         }
  2109.         if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) {
  2110.              if (deltaA > 0xffff)
  2111.                   goto uncompressed;
  2112.              ENCODE(deltaA);
  2113.              changes |= NEW_A;
  2114.         }
  2115.         if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) {
  2116.              if (deltaS > 0xffff)
  2117.                   goto uncompressed;
  2118.              ENCODE(deltaS);
  2119.              changes |= NEW_S;
  2120.         }
  2121.         /*
  2122.          * Look for the special-case encodings.
  2123.          */
  2124.         switch (changes) {
  2125.  
  2126.         case 0:
  2127.              /*
  2128.               * Nothing changed. If this packet contains data and the last
  2129.               * one didn't, this is probably a data packet following an
  2130.               * ack (normal on an interactive connection) and we send it
  2131.               * compressed.  Otherwise it's probably a retransmit,
  2132.               * retransmitted ack or window probe.  Send it uncompressed
  2133.               * in case the other side missed the compressed version.
  2134.               */
  2135.              if (ip->ip_len != cs->cs_ip.ip_len &&
  2136.                  ntohs(cs->cs_ip.ip_len) == hlen)
  2137.                   break;
  2138.  
  2139.              /* (fall through) */
  2140.  
  2141.         case SPECIAL_I:
  2142.  
  2143.  
  2144.    Jacobson                                                       [Page 34]
  2145.  
  2146.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2147.  
  2148.  
  2149.         case SPECIAL_D:
  2150.              /*
  2151.               * Actual changes match one of our special case encodings --
  2152.               * send packet uncompressed.
  2153.               */
  2154.              goto uncompressed;
  2155.  
  2156.         case NEW_S | NEW_A:
  2157.              if (deltaS == deltaA &&
  2158.                  deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
  2159.                   /* special case for echoed terminal traffic */
  2160.                   changes = SPECIAL_I;
  2161.                   cp = new_seq;
  2162.              }
  2163.              break;
  2164.  
  2165.         case NEW_S:
  2166.              if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
  2167.                   /* special case for data xfer */
  2168.                   changes = SPECIAL_D;
  2169.                   cp = new_seq;
  2170.              }
  2171.              break;
  2172.         }
  2173.         deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);
  2174.         if (deltaS != 1) {
  2175.              ENCODEZ(deltaS);
  2176.              changes |= NEW_I;
  2177.         }
  2178.         if (th->th_flags & TH_PUSH)
  2179.              changes |= TCP_PUSH_BIT;
  2180.         /*
  2181.          * Grab the cksum before we overwrite it below.  Then update our
  2182.          * state with this packet's header.
  2183.          */
  2184.         deltaA = ntohs(th->th_sum);
  2185.         BCOPY(ip, &cs->cs_ip, hlen);
  2186.  
  2187.         /*
  2188.          * We want to use the original packet as our compressed packet. (cp -
  2189.          * new_seq) is the number of bytes we need for compressed sequence
  2190.          * numbers.  In addition we need one byte for the change mask, one
  2191.          * for the connection id and two for the tcp checksum. So, (cp -
  2192.          * new_seq) + 4 bytes of header are needed.  hlen is how many bytes
  2193.          * of the original packet to toss so subtract the two to get the new
  2194.          * packet size.
  2195.          */
  2196.         deltaS = cp - new_seq;
  2197.         cp = (u_char *) ip;
  2198.         if (compress_cid == 0 || comp->last_xmit != cs->cs_id) {
  2199.              comp->last_xmit = cs->cs_id;
  2200.  
  2201.  
  2202.    Jacobson                                                       [Page 35]
  2203.  
  2204.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2205.  
  2206.  
  2207.              hlen -= deltaS + 4;
  2208.              cp += hlen;
  2209.              *cp++ = changes | NEW_C;
  2210.              *cp++ = cs->cs_id;
  2211.         } else {
  2212.              hlen -= deltaS + 3;
  2213.              cp += hlen;
  2214.              *cp++ = changes;
  2215.         }
  2216.         m->m_len -= hlen;
  2217.         m->m_off += hlen;
  2218.         *cp++ = deltaA >> 8;
  2219.         *cp++ = deltaA;
  2220.         BCOPY(new_seq, cp, deltaS);
  2221.         return (TYPE_COMPRESSED_TCP);
  2222.  
  2223.    uncompressed:
  2224.         /*
  2225.          * Update connection state cs & send uncompressed packet
  2226.          * ('uncompressed' means a regular ip/tcp packet but with the
  2227.          * 'conversation id' we hope to use on future compressed packets in
  2228.          * the protocol field).
  2229.          */
  2230.         BCOPY(ip, &cs->cs_ip, hlen);
  2231.         ip->ip_p = cs->cs_id;
  2232.         comp->last_xmit = cs->cs_id;
  2233.         return (TYPE_UNCOMPRESSED_TCP);
  2234.    }
  2235.  
  2236.  
  2237.  
  2238.  
  2239.  
  2240.  
  2241.  
  2242.  
  2243.  
  2244.  
  2245.  
  2246.  
  2247.  
  2248.  
  2249.  
  2250.  
  2251.  
  2252.  
  2253.  
  2254.  
  2255.  
  2256.  
  2257.  
  2258.  
  2259.  
  2260.    Jacobson                                                       [Page 36]
  2261.  
  2262.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2263.  
  2264.  
  2265.    A.3  Decompression
  2266.  
  2267.    This routine decompresses a received packet.  It is called with a
  2268.    pointer to the packet, the packet length and type, and a pointer to the
  2269.    compression state structure for the incoming serial line.  It returns a
  2270.    pointer to the resulting packet or zero if there were errors in the
  2271.    incoming packet.  If the packet is COMPRESSED_TCP or UNCOMPRESSED_TCP,
  2272.    the compression state will be updated.
  2273.  
  2274.    The new packet will be constructed in-place.  That means that there must
  2275.    be 128 bytes of free space in front of bufp to allow room for the
  2276.    reconstructed IP and TCP headers.  The reconstructed packet will be
  2277.    aligned on a 32-bit boundary.
  2278.  
  2279.    u_char *
  2280.    sl_uncompress_tcp(bufp, len, type, comp)
  2281.         u_char *bufp;
  2282.         int len;
  2283.         u_int type;
  2284.         struct slcompress *comp;
  2285.    {
  2286.         register u_char *cp;
  2287.         register u_int hlen, changes;
  2288.         register struct tcphdr *th;
  2289.         register struct cstate *cs;
  2290.         register struct ip *ip;
  2291.  
  2292.         switch (type) {
  2293.  
  2294.         case TYPE_ERROR:
  2295.         default:
  2296.              goto bad;
  2297.  
  2298.         case TYPE_IP:
  2299.              return (bufp);
  2300.  
  2301.         case TYPE_UNCOMPRESSED_TCP:
  2302.              /*
  2303.               * Locate the saved state for this connection.  If the state
  2304.               * index is legal, clear the 'discard' flag.
  2305.               */
  2306.              ip = (struct ip *) bufp;
  2307.              if (ip->ip_p >= MAX_STATES)
  2308.                   goto bad;
  2309.  
  2310.              cs = &comp->rstate[comp->last_recv = ip->ip_p];
  2311.              comp->flags &= ~SLF_TOSS;
  2312.              /*
  2313.               * Restore the IP protocol field then save a copy of this
  2314.               * packet header.  (The checksum is zeroed in the copy so we
  2315.               * don't have to zero it each time we process a compressed
  2316.  
  2317.  
  2318.    Jacobson                                                       [Page 37]
  2319.  
  2320.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2321.  
  2322.  
  2323.               * packet.
  2324.               */
  2325.              ip->ip_p = IPPROTO_TCP;
  2326.              hlen = ip->ip_hl;
  2327.              hlen += ((struct tcphdr *) & ((int *) ip)[hlen])->th_off;
  2328.              hlen <<= 2;
  2329.              BCOPY(ip, &cs->cs_ip, hlen);
  2330.              cs->cs_ip.ip_sum = 0;
  2331.              cs->cs_hlen = hlen;
  2332.              return (bufp);
  2333.  
  2334.         case TYPE_COMPRESSED_TCP:
  2335.              break;
  2336.         }
  2337.         /* We've got a compressed packet. */
  2338.         cp = bufp;
  2339.         changes = *cp++;
  2340.         if (changes & NEW_C) {
  2341.              /*
  2342.               * Make sure the state index is in range, then grab the
  2343.               * state. If we have a good state index, clear the 'discard'
  2344.               * flag.
  2345.               */
  2346.              if (*cp >= MAX_STATES)
  2347.                   goto bad;
  2348.  
  2349.              comp->flags &= ~SLF_TOSS;
  2350.              comp->last_recv = *cp++;
  2351.         } else {
  2352.              /*
  2353.               * This packet has an implicit state index.  If we've had a
  2354.               * line error since the last time we got an explicit state
  2355.               * index, we have to toss the packet.
  2356.               */
  2357.              if (comp->flags & SLF_TOSS)
  2358.                   return ((u_char *) 0);
  2359.         }
  2360.         /*
  2361.          * Find the state then fill in the TCP checksum and PUSH bit.
  2362.          */
  2363.         cs = &comp->rstate[comp->last_recv];
  2364.         hlen = cs->cs_ip.ip_hl << 2;
  2365.         th = (struct tcphdr *) & ((u_char *) &cs->cs_ip)[hlen];
  2366.         th->th_sum = htons((*cp << 8) | cp[1]);
  2367.         cp += 2;
  2368.         if (changes & TCP_PUSH_BIT)
  2369.              th->th_flags |= TH_PUSH;
  2370.         else
  2371.              th->th_flags &= ~TH_PUSH;
  2372.  
  2373.         /*
  2374.  
  2375.  
  2376.    Jacobson                                                       [Page 38]
  2377.  
  2378.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2379.  
  2380.  
  2381.          * Fix up the state's ack, seq, urg and win fields based on the
  2382.          * changemask.
  2383.          */
  2384.         switch (changes & SPECIALS_MASK) {
  2385.         case SPECIAL_I:
  2386.              {
  2387.              register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
  2388.              th->th_ack = htonl(ntohl(th->th_ack) + i);
  2389.              th->th_seq = htonl(ntohl(th->th_seq) + i);
  2390.              }
  2391.              break;
  2392.  
  2393.         case SPECIAL_D:
  2394.              th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)
  2395.                           - cs->cs_hlen);
  2396.              break;
  2397.  
  2398.         default:
  2399.              if (changes & NEW_U) {
  2400.                   th->th_flags |= TH_URG;
  2401.                   DECODEU(th->th_urp)
  2402.              } else
  2403.                   th->th_flags &= ~TH_URG;
  2404.              if (changes & NEW_W)
  2405.                   DECODES(th->th_win)
  2406.              if (changes & NEW_A)
  2407.                   DECODEL(th->th_ack)
  2408.              if (changes & NEW_S)
  2409.                   DECODEL(th->th_seq)
  2410.              break;
  2411.         }
  2412.         /* Update the IP ID */
  2413.         if (changes & NEW_I)
  2414.              DECODES(cs->cs_ip.ip_id)
  2415.         else
  2416.              cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);
  2417.  
  2418.         /*
  2419.          * At this point, cp points to the first byte of data in the packet.
  2420.          * If we're not aligned on a 4-byte boundary, copy the data down so
  2421.          * the IP & TCP headers will be aligned.  Then back up cp by the
  2422.          * TCP/IP header length to make room for the reconstructed header (we
  2423.          * assume the packet we were handed has enough space to prepend 128
  2424.          * bytes of header).  Adjust the lenth to account for the new header
  2425.          * & fill in the IP total length.
  2426.          */
  2427.         len -= (cp - bufp);
  2428.         if (len < 0)
  2429.              /*
  2430.               * we must have dropped some characters (crc should detect
  2431.               * this but the old slip framing won't)
  2432.  
  2433.  
  2434.    Jacobson                                                       [Page 39]
  2435.  
  2436.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2437.  
  2438.  
  2439.               */
  2440.              goto bad;
  2441.  
  2442.         if ((int) cp & 3) {
  2443.              if (len > 0)
  2444.                   OVBCOPY(cp, (int) cp & ~3, len);
  2445.              cp = (u_char *) ((int) cp & ~3);
  2446.         }
  2447.         cp -= cs->cs_hlen;
  2448.         len += cs->cs_hlen;
  2449.         cs->cs_ip.ip_len = htons(len);
  2450.         BCOPY(&cs->cs_ip, cp, cs->cs_hlen);
  2451.  
  2452.         /* recompute the ip header checksum */
  2453.         {
  2454.              register u_short *bp = (u_short *) cp;
  2455.              for (changes = 0; hlen > 0; hlen -= 2)
  2456.                   changes += *bp++;
  2457.              changes = (changes & 0xffff) + (changes >> 16);
  2458.              changes = (changes & 0xffff) + (changes >> 16);
  2459.              ((struct ip *) cp)->ip_sum = ~changes;
  2460.         }
  2461.         return (cp);
  2462.  
  2463.    bad:
  2464.         comp->flags |= SLF_TOSS;
  2465.         return ((u_char *) 0);
  2466.    }
  2467.  
  2468.  
  2469.  
  2470.  
  2471.  
  2472.  
  2473.  
  2474.  
  2475.  
  2476.  
  2477.  
  2478.  
  2479.  
  2480.  
  2481.  
  2482.  
  2483.  
  2484.  
  2485.  
  2486.  
  2487.  
  2488.  
  2489.  
  2490.  
  2491.  
  2492.    Jacobson                                                       [Page 40]
  2493.  
  2494.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2495.  
  2496.  
  2497.    A.4  Initialization
  2498.  
  2499.    This routine initializes the state structure for both the transmit and
  2500.    receive halves of some serial line.  It must be called each time the
  2501.    line is brought up.
  2502.  
  2503.    void
  2504.    sl_compress_init(comp)
  2505.         struct slcompress *comp;
  2506.    {
  2507.         register u_int i;
  2508.         register struct cstate *tstate = comp->tstate;
  2509.  
  2510.         /*
  2511.          * Clean out any junk left from the last time line was used.
  2512.          */
  2513.         bzero((char *) comp, sizeof(*comp));
  2514.         /*
  2515.          * Link the transmit states into a circular list.
  2516.          */
  2517.         for (i = MAX_STATES - 1; i > 0; --i) {
  2518.              tstate[i].cs_id = i;
  2519.              tstate[i].cs_next = &tstate[i - 1];
  2520.         }
  2521.         tstate[0].cs_next = &tstate[MAX_STATES - 1];
  2522.         tstate[0].cs_id = 0;
  2523.         comp->last_cs = &tstate[0];
  2524.         /*
  2525.          * Make sure we don't accidentally do CID compression
  2526.          * (assumes MAX_STATES < 255).
  2527.          */
  2528.         comp->last_recv = 255;
  2529.         comp->last_xmit = 255;
  2530.    }
  2531.  
  2532.  
  2533.    A.5  Berkeley Unix dependencies
  2534.  
  2535.    Note:  The following is of interest only if you are trying to bring the
  2536.    sample code up on a system that is not derived from 4BSD (Berkeley
  2537.    Unix).
  2538.  
  2539.    The code uses the normal Berkeley Unix header files (from
  2540.    /usr/include/netinet) for definitions of the structure of IP and TCP
  2541.    headers.  The structure tags tend to follow the protocol RFCs closely
  2542.    and should be obvious even if you do not have access to a 4BSD
  2543.    system./48/
  2544.  
  2545.    ----------------------------
  2546.     48. In the event they are not obvious, the header files (and all the
  2547.    Berkeley networking code) can be anonymous ftp'd from host
  2548.  
  2549.  
  2550.    Jacobson                                                       [Page 41]
  2551.  
  2552.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2553.  
  2554.  
  2555.    The macro BCOPY(src, dst, amt) is invoked to copy amt bytes from src to
  2556.    dst.  In BSD, it translates into a call to bcopy.  If you have the
  2557.    misfortune to be running System-V Unix, it can be translated into a call
  2558.    to memcpy.  The macro OVBCOPY(src, dst, amt) is used to copy when src
  2559.    and dst overlap (i.e., when doing the 4-byte alignment copy).  In the
  2560.    BSD kernel, it translates into a call to ovbcopy.  Since AT&T botched
  2561.    the definition of memcpy, this should probably translate into a copy
  2562.    loop under System-V.
  2563.  
  2564.    The macro BCMP(src, dst, amt) is invoked to compare amt bytes of src and
  2565.    dst for equality.  In BSD, it translates into a call to bcmp.  In
  2566.    System-V, it can be translated into a call to memcmp or you can write a
  2567.    routine to do the compare.  The routine should return zero if all bytes
  2568.    of src and dst are equal and non-zero otherwise.
  2569.  
  2570.    The routine ntohl(dat) converts (4 byte) long dat from network byte
  2571.    order to host byte order.  On a reasonable cpu this can be the no-op
  2572.    macro:
  2573.                            #define ntohl(dat) (dat)
  2574.  
  2575.    On a Vax or IBM PC (or anything with Intel byte order), you will have to
  2576.    define a macro or routine to rearrange bytes.
  2577.  
  2578.    The routine ntohs(dat) is like ntohl but converts (2 byte) shorts
  2579.    instead of longs.  The routines htonl(dat) and htons(dat) do the inverse
  2580.    transform (host to network byte order) for longs and shorts.
  2581.  
  2582.    A struct mbuf is used in the call to sl_compress_tcp because that
  2583.    routine needs to modify both the start address and length if the
  2584.    incoming packet is compressed.  In BSD, an mbuf is the kernel's buffer
  2585.    management structure.  If other systems, the following definition should
  2586.    be sufficient:
  2587.  
  2588.             struct mbuf {
  2589.                     u_char  *m_off; /* pointer to start of data */
  2590.                     int     m_len;  /* length of data */
  2591.             };
  2592.  
  2593.             #define mtod(m, t) ((t)(m->m_off))
  2594.  
  2595.  
  2596.  
  2597.  
  2598.  
  2599.  
  2600.  
  2601.  
  2602.  
  2603.  
  2604.    ----------------------------
  2605.    ucbarpa.berkeley.edu, files pub/4.3/tcp.tar and pub/4.3/inet.tar.
  2606.  
  2607.  
  2608.    Jacobson                                                       [Page 42]
  2609.  
  2610.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2611.  
  2612.  
  2613.    B  Compatibility with past mistakes
  2614.  
  2615.  
  2616.    When combined with the modern PPP serial line protocol[9], the use of
  2617.    header compression is automatic and invisible to the user.
  2618.    Unfortunately, many sites have existing users of the SLIP described in
  2619.    [12] which doesn't allow for different protocol types to distinguish
  2620.    header compressed packets from IP packets or for version numbers or an
  2621.    option exchange that could be used to automatically negotiate header
  2622.    compression.
  2623.  
  2624.    The author has used the following tricks to allow header compressed SLIP
  2625.    to interoperate with the existing servers and clients.  Note that these
  2626.    are hacks for compatibility with past mistakes and should be offensive
  2627.    to any right thinking person.  They are offered solely to ease the pain
  2628.    of running SLIP while users wait patiently for vendors to release PPP.
  2629.  
  2630.  
  2631.    B.1  Living without a framing `type' byte
  2632.  
  2633.    The bizarre packet type numbers in sec. A.1 were chosen to allow a
  2634.    `packet type' to be sent on lines where it is undesirable or impossible
  2635.    to add an explicit type byte.  Note that the first byte of an IP packet
  2636.    always contains `4' (the IP protocol version) in the top four bits.  And
  2637.    that the most significant bit of the first byte of the compressed header
  2638.    is ignored.  Using the packet types in sec. A.1, the type can be encoded
  2639.    in the most significant bits of the outgoing packet using the code
  2640.  
  2641.                     p->dat[0] |= sl_compress_tcp(p, comp);
  2642.  
  2643.     and decoded on the receive side by
  2644.  
  2645.                   if (p->dat[0] & 0x80)
  2646.                           type = TYPE_COMPRESSED_TCP;
  2647.                   else if (p->dat[0] >= 0x70) {
  2648.                           type = TYPE_UNCOMPRESSED_TCP;
  2649.                           p->dat[0] &=~ 0x30;
  2650.                   } else
  2651.                           type = TYPE_IP;
  2652.                   status = sl_uncompress_tcp(p, type, comp);
  2653.  
  2654.  
  2655.  
  2656.  
  2657.  
  2658.  
  2659.    B.2  Backwards compatible SLIP servers
  2660.  
  2661.    The SLIP described in [12] doesn't include any mechanism that could be
  2662.    used to automatically negotiate header compression.  It would be nice to
  2663.  
  2664.  
  2665.  
  2666.    Jacobson                                                       [Page 43]
  2667.  
  2668.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2669.  
  2670.  
  2671.    allow users of this SLIP to use header compression but, when users of
  2672.    the two SLIP varients share a common server, it would be annoying and
  2673.    difficult to manually configure both ends of each connection to enable
  2674.    compression.  The following procedure can be used to avoid manual
  2675.    configuration.
  2676.  
  2677.    Since there are two types of dial-in clients (those that implement
  2678.    compression and those that don't) but one server for both types, it's
  2679.    clear that the server will be reconfiguring for each new client session
  2680.    but clients change configuration seldom if ever.  If manual
  2681.    configuration has to be done, it should be done on the side that changes
  2682.    infrequently --- the client.  This suggests that the server should
  2683.    somehow learn from the client whether to use header compression.
  2684.    Assuming symmetry (i.e., if compression is used at all it should be used
  2685.    both directions) the server can use the receipt of a compressed packet
  2686.    from some client to indicate that it can send compressed packets to that
  2687.    client.  This leads to the following algorithm:
  2688.  
  2689.    There are two bits per line to control header compression:  allowed and
  2690.    on.  If on is set, compressed packets are sent, otherwise not.  If
  2691.    allowed is set, compressed packets can be received and, if an
  2692.    UNCOMPRESSED_TCP packet arrives when on is clear, on will be set./49/
  2693.    If a compressed packet arrives when allowed is clear, it will be
  2694.    ignored.
  2695.  
  2696.    Clients are configured with both bits set (allowed is always set if on
  2697.    is set) and the server starts each session with allowed set and on
  2698.    clear.  The first compressed packet from the client (which must be a
  2699.    UNCOMPRESSED_TCP packet) turns on compression for the server.
  2700.  
  2701.  
  2702.  
  2703.  
  2704.  
  2705.  
  2706.  
  2707.  
  2708.  
  2709.  
  2710.  
  2711.  
  2712.  
  2713.  
  2714.  
  2715.  
  2716.    ----------------------------
  2717.     49. Since [12] framing doesn't include error detection, one should be
  2718.    careful not to `false trigger' compression on the server.  The
  2719.    UNCOMPRESSED_TCP packet should checked for consistency (e.g., IP
  2720.    checksum correctness) before compression is enabled.  Arrival of
  2721.    COMPRESSED_TCP packets should not be used to enable compression.
  2722.  
  2723.  
  2724.    Jacobson                                                       [Page 44]
  2725.  
  2726.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2727.  
  2728.  
  2729.    C  More aggressive compression
  2730.  
  2731.  
  2732.    As noted in sec. 3.2.2, easily detected patterns exist in the stream of
  2733.    compressed headers, indicating that more compression could be done.
  2734.    Would this be worthwhile?
  2735.  
  2736.    The average compressed datagram has only seven bits of header./50/  The
  2737.    framing must be at least one bit (to encode the `type') and will
  2738.    probably be more like two to three bytes.  In most interesting cases
  2739.    there will be at least one byte of data.  Finally, the end-to-end
  2740.    check---the TCP checksum---must be passed through unmodified./51/
  2741.  
  2742.    The framing, data and checksum will remain even if the header is
  2743.    completely compressed out so the change in average packet size is, at
  2744.    best, four bytes down to three bytes and one bit --- roughly a 25%
  2745.    improvement in delay./52/  While this may seem significant, on a 2400
  2746.    bps line it means that typing echo response takes 25 rather than 29 ms.
  2747.    At the present stage of human evolution, this difference is not
  2748.    detectable.
  2749.  
  2750.    However, the author sheepishly admits to perverting this compression
  2751.    scheme for a very special case data-acquisition problem:  We had an
  2752.    instrument and control package floating at 200KV, communicating with
  2753.    ground level via a telemetry system.  For many reasons (multiplexed
  2754.    communication, pipelining, error recovery, availability of well tested
  2755.    implementations, etc.), it was convenient to talk to the package using
  2756.    TCP/IP. However, since the primary use of the telemetry link was data
  2757.    acquisition, it was designed with an uplink channel capacity <0.5% the
  2758.    downlink's.  To meet application delay budgets, data packets were 100
  2759.    bytes and, since TCP acks every other packet, the relative uplink
  2760.    bandwidth for acks is a/200 where `a' is the total size of ack packets.
  2761.    Using the scheme in this paper, the smallest ack is four bytes which
  2762.    would imply an uplink bandwidth 2% of the downlink.  This wasn't
  2763.  
  2764.    ----------------------------
  2765.     50. Tests run with several million packets from a mixed traffic load
  2766.    (i.e., statistics kept on a year's traffic from my home to work) show
  2767.    that 80% of packets use one of the two special encodings and, thus, the
  2768.    only header is the change mask.
  2769.     51. If someone tries to sell you a scheme that compresses the TCP
  2770.    checksum `Just say no'.  Some poor fool has yet to have the sad
  2771.    experience that reveals the end-to-end argument is gospel truth.  Worse,
  2772.    since the fool is subverting your end-to-end error check, you may pay
  2773.    the price for this education and they will be none the wiser.  What does
  2774.    it profit a man to gain two byte times of delay and lose peace of mind?
  2775.     52. Note again that we must be concerned about interactive delay to be
  2776.    making this argument:  Bulk data transfer performance will be dominated
  2777.    by the time to send the data and the difference between three and four
  2778.    byte headers on a datagram containing tens or hundreds of data bytes is,
  2779.    practically, no difference.
  2780.  
  2781.  
  2782.    Jacobson                                                       [Page 45]
  2783.  
  2784.    RFC 1144               Compressing TCP/IP Headers          February 1990
  2785.  
  2786.  
  2787.    possible so we used the scheme described in footnote 15:  If the first
  2788.    bit of the frame was one, it meant `same compressed header as last
  2789.    time'.  Otherwise the next two bits gave one of the types described in
  2790.    sec. 3.2.  Since the link had excellent forward error correction and
  2791.    traffic made only a single hop, the TCP checksum was compressed out
  2792.    (blush!) of the `same header' packet types/53/ so the total header size
  2793.    for these packets was one bit.  Over several months of operation, more
  2794.    than 99% of the 40 byte TCP/IP headers were compressed down to one
  2795.    bit./54/
  2796.  
  2797.  
  2798.    D  Security Considerations
  2799.  
  2800.  
  2801.    Security considerations are not addressed in this memo.
  2802.  
  2803.  
  2804.    E  Author's address
  2805.  
  2806.  
  2807.        Address:  Van Jacobson
  2808.                  Real Time Systems Group
  2809.                  Mail Stop 46A
  2810.                  Lawrence Berkeley Laboratory
  2811.                  Berkeley, CA 94720
  2812.  
  2813.        Phone:    Use email (author ignores his phone)
  2814.  
  2815.        EMail:    van@helios.ee.lbl.gov
  2816.  
  2817.  
  2818.  
  2819.  
  2820.  
  2821.  
  2822.  
  2823.  
  2824.  
  2825.  
  2826.  
  2827.  
  2828.  
  2829.  
  2830.    ----------------------------
  2831.     53. The checksum was re-generated in the decompressor and, of course,
  2832.    the `toss' logic was made considerably more aggressive to prevent error
  2833.    propagation.
  2834.     54. We have heard the suggestion that `real-time' needs require
  2835.    abandoning TCP/IP in favor of a `light-weight' protocol with smaller
  2836.    headers.  It is difficult to envision a protocol that averages less than
  2837.    one header bit per packet.
  2838.  
  2839.  
  2840.    Jacobson                                                       [Page 46]
  2841.  
  2842.